160682025-03-30 11:42:14szilMetróutasokcpp17Partially correct 25/10041ms2804 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 > min(v[i], curr)) {
                        return false;
                    }
                    curr += v[i] - max(0ll, 2 * need);
                } else {
                    curr += v[i];
                }
            }

            return true;
        };

        auto calc = [&]() {
            ll lo = 0, hi = INF;
            while (lo < hi) {
                ll mid = (lo + hi) / 2;
                if (f(mid)) {
                    hi = mid;
                } else {
                    lo = mid + 1;
                }
            }
            reverse(v.begin()+1, v.end());
            return lo;
        };

        ll ans = calc();
        ans = min(ans, calc());

        cout << ans << "\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
1Accepted1ms316 KiB
2Partially correct37ms2612 KiB
subtask23/12
3Accepted1ms508 KiB
4Accepted1ms316 KiB
5Partially correct1ms316 KiB
6Partially correct1ms500 KiB
7Accepted1ms316 KiB
8Accepted1ms316 KiB
9Partially correct1ms404 KiB
10Accepted1ms316 KiB
11Accepted1ms316 KiB
12Accepted1ms316 KiB
13Partially correct1ms316 KiB
14Partially correct1ms316 KiB
15Accepted1ms548 KiB
16Accepted1ms380 KiB
subtask33/12
17Accepted1ms508 KiB
18Accepted1ms316 KiB
19Partially correct1ms316 KiB
20Partially correct1ms500 KiB
21Accepted1ms316 KiB
22Accepted1ms316 KiB
23Partially correct1ms404 KiB
24Accepted1ms316 KiB
25Accepted1ms316 KiB
26Accepted1ms316 KiB
27Accepted1ms316 KiB
28Partially correct1ms316 KiB
29Accepted1ms316 KiB
30Partially correct1ms316 KiB
31Partially correct1ms316 KiB
32Partially correct1ms316 KiB
33Partially correct1ms316 KiB
34Partially correct1ms316 KiB
35Partially correct1ms316 KiB
36Accepted1ms316 KiB
37Partially correct1ms316 KiB
38Partially correct1ms316 KiB
39Partially correct1ms316 KiB
40Accepted1ms532 KiB
41Partially correct1ms316 KiB
42Accepted1ms548 KiB
43Accepted1ms548 KiB
44Accepted1ms380 KiB
45Accepted1ms360 KiB
46Accepted1ms328 KiB
47Partially correct1ms316 KiB
48Accepted1ms316 KiB
49Accepted1ms316 KiB
subtask44/16
50Accepted1ms508 KiB
51Accepted1ms316 KiB
52Partially correct1ms316 KiB
53Partially correct1ms500 KiB
54Accepted1ms316 KiB
55Accepted1ms316 KiB
56Partially correct1ms404 KiB
57Accepted1ms316 KiB
58Accepted1ms316 KiB
59Accepted1ms316 KiB
60Accepted1ms316 KiB
61Partially correct1ms316 KiB
62Accepted1ms316 KiB
63Partially correct1ms316 KiB
64Partially correct1ms316 KiB
65Partially correct1ms316 KiB
66Partially correct1ms316 KiB
67Partially correct1ms316 KiB
68Partially correct1ms316 KiB
69Accepted1ms316 KiB
70Accepted1ms368 KiB
71Partially correct1ms316 KiB
72Partially correct1ms316 KiB
73Partially correct1ms540 KiB
74Partially correct1ms316 KiB
75Accepted1ms508 KiB
76Partially correct1ms316 KiB
77Accepted1ms524 KiB
78Partially correct1ms316 KiB
79Partially correct1ms556 KiB
80Partially correct1ms316 KiB
81Partially correct1ms316 KiB
82Partially correct1ms316 KiB
83Accepted1ms532 KiB
84Partially correct1ms316 KiB
85Accepted1ms548 KiB
86Accepted1ms548 KiB
87Accepted1ms380 KiB
88Accepted1ms360 KiB
89Accepted1ms328 KiB
90Partially correct1ms316 KiB
91Accepted1ms316 KiB
92Accepted1ms316 KiB
subtask515/60
93Accepted1ms508 KiB
94Partially correct37ms2612 KiB
95Accepted1ms316 KiB
96Partially correct1ms316 KiB
97Partially correct1ms500 KiB
98Accepted1ms316 KiB
99Accepted1ms316 KiB
100Partially correct1ms404 KiB
101Accepted1ms316 KiB
102Accepted1ms316 KiB
103Accepted1ms316 KiB
104Accepted1ms316 KiB
105Partially correct1ms316 KiB
106Accepted1ms316 KiB
107Partially correct1ms316 KiB
108Partially correct1ms316 KiB
109Partially correct1ms316 KiB
110Partially correct1ms316 KiB
111Partially correct1ms316 KiB
112Partially correct1ms316 KiB
113Accepted1ms316 KiB
114Accepted1ms368 KiB
115Partially correct1ms316 KiB
116Partially correct1ms316 KiB
117Partially correct1ms540 KiB
118Partially correct1ms316 KiB
119Accepted1ms508 KiB
120Partially correct1ms316 KiB
121Accepted1ms524 KiB
122Partially correct1ms316 KiB
123Partially correct1ms556 KiB
124Partially correct39ms2788 KiB
125Partially correct37ms2788 KiB
126Partially correct41ms2788 KiB
127Partially correct35ms2804 KiB
128Partially correct39ms2796 KiB
129Partially correct41ms2612 KiB
130Partially correct37ms2768 KiB
131Accepted41ms2804 KiB
132Partially correct41ms2784 KiB
133Partially correct1ms316 KiB
134Partially correct1ms316 KiB
135Partially correct1ms316 KiB
136Accepted1ms532 KiB
137Partially correct1ms316 KiB
138Accepted1ms548 KiB
139Accepted1ms548 KiB
140Accepted1ms380 KiB
141Accepted1ms360 KiB
142Accepted1ms328 KiB
143Partially correct1ms316 KiB
144Accepted25ms2612 KiB
145Accepted21ms2356 KiB
146Partially correct25ms2612 KiB
147Accepted14ms1588 KiB
148Partially correct24ms2608 KiB
149Accepted24ms2356 KiB
150Accepted1ms316 KiB
151Accepted1ms316 KiB
152Accepted24ms2356 KiB