10804 2024. 04. 14 13:14:20 Ablablabla Metróutasok cpp17 Elfogadva 100/100 82ms 6728 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 1876 KiB
2 Elfogadva 82ms 3468 KiB
subtask2 12/12
3 Elfogadva 3ms 2204 KiB
4 Elfogadva 3ms 2276 KiB
5 Elfogadva 3ms 2492 KiB
6 Elfogadva 3ms 2840 KiB
7 Elfogadva 3ms 2788 KiB
8 Elfogadva 3ms 2792 KiB
9 Elfogadva 3ms 2992 KiB
10 Elfogadva 3ms 3156 KiB
11 Elfogadva 3ms 3244 KiB
12 Elfogadva 2ms 3184 KiB
13 Elfogadva 2ms 3072 KiB
14 Elfogadva 3ms 3072 KiB
15 Elfogadva 3ms 3320 KiB
16 Elfogadva 3ms 3284 KiB
subtask3 12/12
17 Elfogadva 3ms 2204 KiB
18 Elfogadva 3ms 2276 KiB
19 Elfogadva 3ms 2492 KiB
20 Elfogadva 3ms 2840 KiB
21 Elfogadva 3ms 2788 KiB
22 Elfogadva 3ms 2792 KiB
23 Elfogadva 3ms 2992 KiB
24 Elfogadva 3ms 3156 KiB
25 Elfogadva 3ms 3244 KiB
26 Elfogadva 2ms 3184 KiB
27 Elfogadva 3ms 3284 KiB
28 Elfogadva 3ms 3420 KiB
29 Elfogadva 3ms 3544 KiB
30 Elfogadva 3ms 3640 KiB
31 Elfogadva 3ms 3852 KiB
32 Elfogadva 3ms 4240 KiB
33 Elfogadva 3ms 4156 KiB
34 Elfogadva 3ms 4284 KiB
35 Elfogadva 3ms 4408 KiB
36 Elfogadva 3ms 4560 KiB
37 Elfogadva 2ms 3072 KiB
38 Elfogadva 3ms 3072 KiB
39 Elfogadva 3ms 4560 KiB
40 Elfogadva 3ms 4688 KiB
41 Elfogadva 3ms 4572 KiB
42 Elfogadva 3ms 4692 KiB
43 Elfogadva 3ms 3320 KiB
44 Elfogadva 3ms 3284 KiB
45 Elfogadva 3ms 4664 KiB
46 Elfogadva 3ms 4664 KiB
47 Elfogadva 3ms 4664 KiB
48 Elfogadva 2ms 4664 KiB
49 Elfogadva 3ms 4784 KiB
subtask4 16/16
50 Elfogadva 3ms 2204 KiB
51 Elfogadva 3ms 2276 KiB
52 Elfogadva 3ms 2492 KiB
53 Elfogadva 3ms 2840 KiB
54 Elfogadva 3ms 2788 KiB
55 Elfogadva 3ms 2792 KiB
56 Elfogadva 3ms 2992 KiB
57 Elfogadva 3ms 3156 KiB
58 Elfogadva 3ms 3244 KiB
59 Elfogadva 2ms 3184 KiB
60 Elfogadva 3ms 3284 KiB
61 Elfogadva 3ms 3420 KiB
62 Elfogadva 3ms 3544 KiB
63 Elfogadva 3ms 3640 KiB
64 Elfogadva 3ms 3852 KiB
65 Elfogadva 3ms 4240 KiB
66 Elfogadva 3ms 4156 KiB
67 Elfogadva 3ms 4284 KiB
68 Elfogadva 3ms 4408 KiB
69 Elfogadva 3ms 4560 KiB
70 Elfogadva 3ms 4668 KiB
71 Elfogadva 3ms 4668 KiB
72 Elfogadva 3ms 4800 KiB
73 Elfogadva 3ms 4812 KiB
74 Elfogadva 3ms 4812 KiB
75 Elfogadva 3ms 4812 KiB
76 Elfogadva 3ms 4808 KiB
77 Elfogadva 3ms 4804 KiB
78 Elfogadva 3ms 4804 KiB
79 Elfogadva 3ms 4804 KiB
80 Elfogadva 2ms 3072 KiB
81 Elfogadva 3ms 3072 KiB
82 Elfogadva 3ms 4560 KiB
83 Elfogadva 3ms 4688 KiB
84 Elfogadva 3ms 4572 KiB
85 Elfogadva 3ms 4692 KiB
86 Elfogadva 3ms 3320 KiB
87 Elfogadva 3ms 3284 KiB
88 Elfogadva 3ms 4664 KiB
89 Elfogadva 3ms 4664 KiB
90 Elfogadva 3ms 4664 KiB
91 Elfogadva 2ms 4664 KiB
92 Elfogadva 3ms 4784 KiB
subtask5 60/60
93 Elfogadva 3ms 2204 KiB
94 Elfogadva 82ms 6160 KiB
95 Elfogadva 3ms 2276 KiB
96 Elfogadva 3ms 2492 KiB
97 Elfogadva 3ms 2840 KiB
98 Elfogadva 3ms 2788 KiB
99 Elfogadva 3ms 2792 KiB
100 Elfogadva 3ms 2992 KiB
101 Elfogadva 3ms 3156 KiB
102 Elfogadva 3ms 3244 KiB
103 Elfogadva 2ms 3184 KiB
104 Elfogadva 3ms 3284 KiB
105 Elfogadva 3ms 3420 KiB
106 Elfogadva 3ms 3544 KiB
107 Elfogadva 3ms 3640 KiB
108 Elfogadva 3ms 3852 KiB
109 Elfogadva 3ms 4240 KiB
110 Elfogadva 3ms 4156 KiB
111 Elfogadva 3ms 4284 KiB
112 Elfogadva 3ms 4408 KiB
113 Elfogadva 3ms 4560 KiB
114 Elfogadva 3ms 4668 KiB
115 Elfogadva 3ms 4668 KiB
116 Elfogadva 3ms 4800 KiB
117 Elfogadva 3ms 4812 KiB
118 Elfogadva 3ms 4812 KiB
119 Elfogadva 3ms 4812 KiB
120 Elfogadva 3ms 4808 KiB
121 Elfogadva 3ms 4804 KiB
122 Elfogadva 3ms 4804 KiB
123 Elfogadva 3ms 4804 KiB
124 Elfogadva 65ms 6288 KiB
125 Elfogadva 65ms 6384 KiB
126 Elfogadva 68ms 6468 KiB
127 Elfogadva 64ms 6476 KiB
128 Elfogadva 67ms 6460 KiB
129 Elfogadva 79ms 6380 KiB
130 Elfogadva 68ms 6376 KiB
131 Elfogadva 64ms 6376 KiB
132 Elfogadva 81ms 6528 KiB
133 Elfogadva 2ms 3072 KiB
134 Elfogadva 3ms 3072 KiB
135 Elfogadva 3ms 4560 KiB
136 Elfogadva 3ms 4688 KiB
137 Elfogadva 3ms 4572 KiB
138 Elfogadva 3ms 4692 KiB
139 Elfogadva 3ms 3320 KiB
140 Elfogadva 3ms 3284 KiB
141 Elfogadva 3ms 4664 KiB
142 Elfogadva 3ms 4664 KiB
143 Elfogadva 3ms 4664 KiB
144 Elfogadva 35ms 6488 KiB
145 Elfogadva 32ms 6620 KiB
146 Elfogadva 37ms 6728 KiB
147 Elfogadva 24ms 5988 KiB
148 Elfogadva 35ms 6452 KiB
149 Elfogadva 32ms 6452 KiB
150 Elfogadva 2ms 4664 KiB
151 Elfogadva 3ms 4784 KiB
152 Elfogadva 32ms 6600 KiB