160672025-03-30 11:39:43szilMetróutasokcpp17Partially correct 25/10028ms2876 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;
        };

        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
1Accepted1ms316 KiB
2Partially correct26ms2612 KiB
subtask23/12
3Accepted1ms508 KiB
4Accepted1ms316 KiB
5Partially correct1ms316 KiB
6Accepted1ms316 KiB
7Accepted1ms316 KiB
8Accepted1ms316 KiB
9Partially correct1ms316 KiB
10Accepted1ms552 KiB
11Accepted1ms316 KiB
12Accepted1ms316 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
24Accepted1ms552 KiB
25Accepted1ms316 KiB
26Accepted1ms316 KiB
27Accepted1ms316 KiB
28Partially correct1ms316 KiB
29Accepted1ms316 KiB
30Accepted1ms508 KiB
31Accepted1ms316 KiB
32Partially correct1ms508 KiB
33Partially correct1ms328 KiB
34Accepted1ms316 KiB
35Accepted1ms316 KiB
36Accepted1ms420 KiB
37Accepted1ms316 KiB
38Partially correct1ms316 KiB
39Partially correct1ms316 KiB
40Accepted1ms316 KiB
41Partially correct1ms508 KiB
42Accepted1ms544 KiB
43Accepted1ms316 KiB
44Accepted1ms316 KiB
45Accepted1ms508 KiB
46Accepted1ms328 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
57Accepted1ms552 KiB
58Accepted1ms316 KiB
59Accepted1ms316 KiB
60Accepted1ms316 KiB
61Partially correct1ms316 KiB
62Accepted1ms316 KiB
63Accepted1ms508 KiB
64Accepted1ms316 KiB
65Partially correct1ms508 KiB
66Partially correct1ms328 KiB
67Accepted1ms316 KiB
68Accepted1ms316 KiB
69Accepted1ms420 KiB
70Accepted1ms316 KiB
71Partially correct1ms316 KiB
72Accepted1ms316 KiB
73Partially correct1ms316 KiB
74Partially correct1ms388 KiB
75Accepted1ms316 KiB
76Accepted1ms316 KiB
77Accepted1ms316 KiB
78Partially correct1ms316 KiB
79Accepted1ms316 KiB
80Accepted1ms316 KiB
81Partially correct1ms316 KiB
82Partially correct1ms316 KiB
83Accepted1ms316 KiB
84Partially correct1ms508 KiB
85Accepted1ms544 KiB
86Accepted1ms316 KiB
87Accepted1ms316 KiB
88Accepted1ms508 KiB
89Accepted1ms328 KiB
90Partially correct1ms316 KiB
91Accepted1ms316 KiB
92Accepted1ms316 KiB
subtask515/60
93Accepted1ms508 KiB
94Partially correct26ms2796 KiB
95Accepted1ms316 KiB
96Partially correct1ms316 KiB
97Accepted1ms316 KiB
98Accepted1ms316 KiB
99Accepted1ms316 KiB
100Partially correct1ms316 KiB
101Accepted1ms552 KiB
102Accepted1ms316 KiB
103Accepted1ms316 KiB
104Accepted1ms316 KiB
105Partially correct1ms316 KiB
106Accepted1ms316 KiB
107Accepted1ms508 KiB
108Accepted1ms316 KiB
109Partially correct1ms508 KiB
110Partially correct1ms328 KiB
111Accepted1ms316 KiB
112Accepted1ms316 KiB
113Accepted1ms420 KiB
114Accepted1ms316 KiB
115Partially correct1ms316 KiB
116Accepted1ms316 KiB
117Partially correct1ms316 KiB
118Partially correct1ms388 KiB
119Accepted1ms316 KiB
120Accepted1ms316 KiB
121Accepted1ms316 KiB
122Partially correct1ms316 KiB
123Accepted1ms316 KiB
124Accepted28ms2612 KiB
125Accepted28ms2612 KiB
126Accepted28ms2804 KiB
127Partially correct26ms2804 KiB
128Accepted28ms2616 KiB
129Partially correct28ms2788 KiB
130Partially correct27ms2784 KiB
131Accepted28ms2876 KiB
132Partially correct28ms2612 KiB
133Accepted1ms316 KiB
134Partially correct1ms316 KiB
135Partially correct1ms316 KiB
136Accepted1ms316 KiB
137Partially correct1ms508 KiB
138Accepted1ms544 KiB
139Accepted1ms316 KiB
140Accepted1ms316 KiB
141Accepted1ms508 KiB
142Accepted1ms328 KiB
143Partially correct1ms316 KiB
144Accepted17ms2612 KiB
145Accepted14ms2284 KiB
146Partially correct17ms2692 KiB
147Accepted9ms1756 KiB
148Partially correct17ms2600 KiB
149Accepted17ms2356 KiB
150Accepted1ms316 KiB
151Accepted1ms316 KiB
152Accepted17ms2576 KiB