10803 2024. 04. 14 13:12:06 Ablablabla Metróutasok cpp17 Részben helyes 25/100 85ms 6456 KiB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
vector<ll> szamok;
ll ossz = 0;

bool check(ll hatar){
    ll mn = 0;
    ll mx = 0;

    for(int i = 0; i < n; i++){
        ll mas = mn;

        if(mn >= szamok[i]){
            mn -= szamok[i];
        } else if(mx < szamok[i]){
            mn = szamok[i] - mx;
        } else{
            mn = (mn + szamok[i]) % 2;
        }

        if(mx + szamok[i] <= hatar){
            mx += szamok[i];
        } else{
            ll marad = hatar - mas;
            if((mas + szamok[i] <= hatar) || (szamok[i] <= mx + hatar)){
                mx = hatar + (marad + szamok[i]) % 2;
            } else{
                return false;
            }
        }
    }

    return (mn == 0);
}

void minKer(){
    ll l = max(szamok[0], szamok[n - 1]), r = ossz;
    ll ans = 0;
    while(l <= r){
        ll k = (l + r) / 2;

        if(check(k)){
            ans = k;
            r = k - 1;
        } else{
            l = k + 1;
        }
    }

    cout << ans << "\n";
}

void maxKer(){
    ll fent = 0;
    ll fel = 0;
    ll maxi = 0;
    for(int i = 0; i < n; i++){
        ll felszall = min(szamok[i], ossz / 2 - fel);
        ll leszall = szamok[i] - felszall;

        fent += felszall - leszall;
        fel += felszall;
        maxi = max(maxi, fent);
    }

    cout << maxi << "\n";
}

int main()
{
    cin >> n;

    szamok.assign(n, 0);
    for(ll &x : szamok){
        cin >> x;
        ossz += x;
    }

    minKer();
    maxKer();
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1748 KiB
2 Részben helyes 85ms 3264 KiB
subtask2 3/12
3 Elfogadva 3ms 2244 KiB
4 Elfogadva 3ms 2340 KiB
5 Elfogadva 3ms 2544 KiB
6 Elfogadva 3ms 2796 KiB
7 Elfogadva 3ms 2852 KiB
8 Elfogadva 3ms 2968 KiB
9 Elfogadva 3ms 3188 KiB
10 Elfogadva 3ms 3272 KiB
11 Részben helyes 3ms 3396 KiB
12 Elfogadva 3ms 3480 KiB
13 Elfogadva 3ms 3484 KiB
14 Részben helyes 3ms 3720 KiB
15 Elfogadva 3ms 3868 KiB
16 Elfogadva 3ms 3880 KiB
subtask3 3/12
17 Elfogadva 3ms 2244 KiB
18 Elfogadva 3ms 2340 KiB
19 Elfogadva 3ms 2544 KiB
20 Elfogadva 3ms 2796 KiB
21 Elfogadva 3ms 2852 KiB
22 Elfogadva 3ms 2968 KiB
23 Elfogadva 3ms 3188 KiB
24 Elfogadva 3ms 3272 KiB
25 Részben helyes 3ms 3396 KiB
26 Elfogadva 3ms 3480 KiB
27 Elfogadva 3ms 3892 KiB
28 Elfogadva 3ms 3892 KiB
29 Elfogadva 3ms 3892 KiB
30 Elfogadva 3ms 4040 KiB
31 Elfogadva 3ms 4036 KiB
32 Elfogadva 3ms 4152 KiB
33 Elfogadva 3ms 4148 KiB
34 Elfogadva 3ms 4152 KiB
35 Elfogadva 3ms 4100 KiB
36 Elfogadva 3ms 4212 KiB
37 Elfogadva 3ms 3484 KiB
38 Részben helyes 3ms 3720 KiB
39 Részben helyes 3ms 4216 KiB
40 Részben helyes 3ms 4212 KiB
41 Részben helyes 3ms 4344 KiB
42 Részben helyes 3ms 4432 KiB
43 Elfogadva 3ms 3868 KiB
44 Elfogadva 3ms 3880 KiB
45 Részben helyes 3ms 4424 KiB
46 Részben helyes 3ms 4428 KiB
47 Részben helyes 3ms 4540 KiB
48 Elfogadva 3ms 4564 KiB
49 Részben helyes 3ms 4332 KiB
subtask4 4/16
50 Elfogadva 3ms 2244 KiB
51 Elfogadva 3ms 2340 KiB
52 Elfogadva 3ms 2544 KiB
53 Elfogadva 3ms 2796 KiB
54 Elfogadva 3ms 2852 KiB
55 Elfogadva 3ms 2968 KiB
56 Elfogadva 3ms 3188 KiB
57 Elfogadva 3ms 3272 KiB
58 Részben helyes 3ms 3396 KiB
59 Elfogadva 3ms 3480 KiB
60 Elfogadva 3ms 3892 KiB
61 Elfogadva 3ms 3892 KiB
62 Elfogadva 3ms 3892 KiB
63 Elfogadva 3ms 4040 KiB
64 Elfogadva 3ms 4036 KiB
65 Elfogadva 3ms 4152 KiB
66 Elfogadva 3ms 4148 KiB
67 Elfogadva 3ms 4152 KiB
68 Elfogadva 3ms 4100 KiB
69 Elfogadva 3ms 4212 KiB
70 Részben helyes 3ms 4488 KiB
71 Elfogadva 3ms 4508 KiB
72 Elfogadva 3ms 4528 KiB
73 Elfogadva 3ms 4488 KiB
74 Elfogadva 3ms 4492 KiB
75 Elfogadva 3ms 4680 KiB
76 Elfogadva 3ms 4892 KiB
77 Részben helyes 3ms 4948 KiB
78 Elfogadva 3ms 4960 KiB
79 Elfogadva 3ms 5068 KiB
80 Elfogadva 3ms 3484 KiB
81 Részben helyes 3ms 3720 KiB
82 Részben helyes 3ms 4216 KiB
83 Részben helyes 3ms 4212 KiB
84 Részben helyes 3ms 4344 KiB
85 Részben helyes 3ms 4432 KiB
86 Elfogadva 3ms 3868 KiB
87 Elfogadva 3ms 3880 KiB
88 Részben helyes 3ms 4424 KiB
89 Részben helyes 3ms 4428 KiB
90 Részben helyes 3ms 4540 KiB
91 Elfogadva 3ms 4564 KiB
92 Részben helyes 3ms 4332 KiB
subtask5 15/60
93 Elfogadva 3ms 2244 KiB
94 Részben helyes 85ms 6456 KiB
95 Elfogadva 3ms 2340 KiB
96 Elfogadva 3ms 2544 KiB
97 Elfogadva 3ms 2796 KiB
98 Elfogadva 3ms 2852 KiB
99 Elfogadva 3ms 2968 KiB
100 Elfogadva 3ms 3188 KiB
101 Elfogadva 3ms 3272 KiB
102 Részben helyes 3ms 3396 KiB
103 Elfogadva 3ms 3480 KiB
104 Elfogadva 3ms 3892 KiB
105 Elfogadva 3ms 3892 KiB
106 Elfogadva 3ms 3892 KiB
107 Elfogadva 3ms 4040 KiB
108 Elfogadva 3ms 4036 KiB
109 Elfogadva 3ms 4152 KiB
110 Elfogadva 3ms 4148 KiB
111 Elfogadva 3ms 4152 KiB
112 Elfogadva 3ms 4100 KiB
113 Elfogadva 3ms 4212 KiB
114 Részben helyes 3ms 4488 KiB
115 Elfogadva 3ms 4508 KiB
116 Elfogadva 3ms 4528 KiB
117 Elfogadva 3ms 4488 KiB
118 Elfogadva 3ms 4492 KiB
119 Elfogadva 3ms 4680 KiB
120 Elfogadva 3ms 4892 KiB
121 Részben helyes 3ms 4948 KiB
122 Elfogadva 3ms 4960 KiB
123 Elfogadva 3ms 5068 KiB
124 Elfogadva 65ms 6304 KiB
125 Elfogadva 67ms 6304 KiB
126 Elfogadva 70ms 6304 KiB
127 Elfogadva 67ms 6456 KiB
128 Elfogadva 68ms 6308 KiB
129 Részben helyes 82ms 6388 KiB
130 Részben helyes 70ms 6308 KiB
131 Elfogadva 65ms 6304 KiB
132 Elfogadva 83ms 6308 KiB
133 Elfogadva 3ms 3484 KiB
134 Részben helyes 3ms 3720 KiB
135 Részben helyes 3ms 4216 KiB
136 Részben helyes 3ms 4212 KiB
137 Részben helyes 3ms 4344 KiB
138 Részben helyes 3ms 4432 KiB
139 Elfogadva 3ms 3868 KiB
140 Elfogadva 3ms 3880 KiB
141 Részben helyes 3ms 4424 KiB
142 Részben helyes 3ms 4428 KiB
143 Részben helyes 3ms 4540 KiB
144 Részben helyes 35ms 6176 KiB
145 Részben helyes 32ms 6180 KiB
146 Részben helyes 37ms 6388 KiB
147 Elfogadva 24ms 5740 KiB
148 Részben helyes 35ms 6180 KiB
149 Részben helyes 32ms 6176 KiB
150 Elfogadva 3ms 4564 KiB
151 Részben helyes 3ms 4332 KiB
152 Elfogadva 32ms 6212 KiB