160662025-03-30 11:30:19szilMetróutasokcpp17Partially correct 25/10029ms2804 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll INF = 1e15;

void solve() {
    int n; cin >> n;
    vector<ll> v(n+1), pref(n+2), suff(n+2);
    for (int i = 1; i <= n; i++) cin >> v[i];
    for (int i = 1; i <= n; i++) pref[i] = pref[i-1] + v[i];
    for (int i = n; i >= 1; i--) suff[i] = suff[i+1] + v[i];

    {
        auto f = [&](ll goal) {
            ll curr = 0;
            for (int i = 1; i <= n; i++) {
                if (curr + v[i] > goal) {
                    ll need = (curr + v[i] - goal + 1) / 2;
                    if (need > curr) {
                        return false;
                    }
                    curr += v[i] - 2 * need;
                } else {
                    curr += v[i];
                }
            }

            return true;
        };

        ll lo = 0, hi = INF;
        while (lo < hi) {
            ll mid = (lo + hi) / 2;
            if (f(mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        cout << lo << "\n";
    }

    {
        ll ans = 0;
        for (int i = 1; i <= n; i++) {
            if (pref[i-1] >= suff[i]) ans = max(ans, suff[i]);
            if (suff[i] >= pref[i-1]) ans = max(ans, pref[i-1]);
        }
        cout << ans << "\n";
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1; 
    // cin >> t;
    while (t--) solve();
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms512 KiB
2Partially correct27ms2612 KiB
subtask23/12
3Accepted1ms508 KiB
4Accepted1ms316 KiB
5Partially correct1ms316 KiB
6Accepted1ms316 KiB
7Accepted1ms316 KiB
8Accepted1ms316 KiB
9Partially correct1ms316 KiB
10Accepted1ms500 KiB
11Accepted1ms508 KiB
12Accepted1ms500 KiB
13Accepted1ms316 KiB
14Partially correct1ms316 KiB
15Accepted1ms316 KiB
16Accepted1ms316 KiB
subtask33/12
17Accepted1ms508 KiB
18Accepted1ms316 KiB
19Partially correct1ms316 KiB
20Accepted1ms316 KiB
21Accepted1ms316 KiB
22Accepted1ms316 KiB
23Partially correct1ms316 KiB
24Accepted1ms500 KiB
25Accepted1ms508 KiB
26Accepted1ms500 KiB
27Accepted1ms316 KiB
28Partially correct1ms316 KiB
29Accepted1ms316 KiB
30Accepted1ms316 KiB
31Accepted1ms508 KiB
32Partially correct1ms316 KiB
33Partially correct1ms316 KiB
34Accepted1ms316 KiB
35Accepted1ms320 KiB
36Accepted1ms388 KiB
37Accepted1ms316 KiB
38Partially correct1ms316 KiB
39Partially correct1ms508 KiB
40Accepted1ms316 KiB
41Partially correct1ms316 KiB
42Accepted1ms316 KiB
43Accepted1ms316 KiB
44Accepted1ms316 KiB
45Accepted1ms316 KiB
46Accepted1ms316 KiB
47Partially correct1ms316 KiB
48Accepted1ms316 KiB
49Accepted1ms316 KiB
subtask44/16
50Accepted1ms508 KiB
51Accepted1ms316 KiB
52Partially correct1ms316 KiB
53Accepted1ms316 KiB
54Accepted1ms316 KiB
55Accepted1ms316 KiB
56Partially correct1ms316 KiB
57Accepted1ms500 KiB
58Accepted1ms508 KiB
59Accepted1ms500 KiB
60Accepted1ms316 KiB
61Partially correct1ms316 KiB
62Accepted1ms316 KiB
63Accepted1ms316 KiB
64Accepted1ms508 KiB
65Partially correct1ms316 KiB
66Partially correct1ms316 KiB
67Accepted1ms316 KiB
68Accepted1ms320 KiB
69Accepted1ms388 KiB
70Accepted1ms316 KiB
71Partially correct1ms316 KiB
72Accepted1ms316 KiB
73Partially correct1ms316 KiB
74Partially correct1ms316 KiB
75Accepted1ms316 KiB
76Accepted1ms316 KiB
77Accepted1ms556 KiB
78Partially correct1ms416 KiB
79Accepted1ms316 KiB
80Accepted1ms316 KiB
81Partially correct1ms316 KiB
82Partially correct1ms508 KiB
83Accepted1ms316 KiB
84Partially correct1ms316 KiB
85Accepted1ms316 KiB
86Accepted1ms316 KiB
87Accepted1ms316 KiB
88Accepted1ms316 KiB
89Accepted1ms316 KiB
90Partially correct1ms316 KiB
91Accepted1ms316 KiB
92Accepted1ms316 KiB
subtask515/60
93Accepted1ms508 KiB
94Partially correct27ms2612 KiB
95Accepted1ms316 KiB
96Partially correct1ms316 KiB
97Accepted1ms316 KiB
98Accepted1ms316 KiB
99Accepted1ms316 KiB
100Partially correct1ms316 KiB
101Accepted1ms500 KiB
102Accepted1ms508 KiB
103Accepted1ms500 KiB
104Accepted1ms316 KiB
105Partially correct1ms316 KiB
106Accepted1ms316 KiB
107Accepted1ms316 KiB
108Accepted1ms508 KiB
109Partially correct1ms316 KiB
110Partially correct1ms316 KiB
111Accepted1ms316 KiB
112Accepted1ms320 KiB
113Accepted1ms388 KiB
114Accepted1ms316 KiB
115Partially correct1ms316 KiB
116Accepted1ms316 KiB
117Partially correct1ms316 KiB
118Partially correct1ms316 KiB
119Accepted1ms316 KiB
120Accepted1ms316 KiB
121Accepted1ms556 KiB
122Partially correct1ms416 KiB
123Accepted1ms316 KiB
124Accepted28ms2612 KiB
125Accepted28ms2612 KiB
126Accepted28ms2676 KiB
127Partially correct27ms2804 KiB
128Accepted28ms2612 KiB
129Partially correct29ms2612 KiB
130Partially correct27ms2624 KiB
131Accepted28ms2612 KiB
132Partially correct29ms2612 KiB
133Accepted1ms316 KiB
134Partially correct1ms316 KiB
135Partially correct1ms508 KiB
136Accepted1ms316 KiB
137Partially correct1ms316 KiB
138Accepted1ms316 KiB
139Accepted1ms316 KiB
140Accepted1ms316 KiB
141Accepted1ms316 KiB
142Accepted1ms316 KiB
143Partially correct1ms316 KiB
144Accepted17ms2644 KiB
145Accepted16ms2420 KiB
146Partially correct17ms2612 KiB
147Accepted9ms1588 KiB
148Partially correct17ms2356 KiB
149Accepted17ms2356 KiB
150Accepted1ms316 KiB
151Accepted1ms316 KiB
152Accepted17ms2356 KiB