160652025-03-30 11:28:41szilMetróutasokcpp17Partially correct 0/10029ms3756 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]);
        }
        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 correct27ms3668 KiB
subtask20/12
3Accepted1ms316 KiB
4Accepted1ms316 KiB
5Partially correct1ms316 KiB
6Accepted1ms316 KiB
7Accepted1ms316 KiB
8Accepted1ms316 KiB
9Wrong answer1ms316 KiB
10Accepted1ms316 KiB
11Partially correct1ms420 KiB
12Partially correct1ms316 KiB
13Partially correct1ms316 KiB
14Partially correct1ms316 KiB
15Accepted1ms316 KiB
16Partially correct1ms316 KiB
subtask30/12
17Accepted1ms316 KiB
18Accepted1ms316 KiB
19Partially correct1ms316 KiB
20Accepted1ms316 KiB
21Accepted1ms316 KiB
22Accepted1ms316 KiB
23Wrong answer1ms316 KiB
24Accepted1ms316 KiB
25Partially correct1ms420 KiB
26Partially correct1ms316 KiB
27Accepted1ms316 KiB
28Partially correct1ms316 KiB
29Accepted1ms316 KiB
30Accepted1ms564 KiB
31Partially correct1ms316 KiB
32Partially correct1ms316 KiB
33Partially correct1ms420 KiB
34Partially correct1ms508 KiB
35Partially correct1ms316 KiB
36Accepted1ms316 KiB
37Partially correct1ms316 KiB
38Partially correct1ms316 KiB
39Partially correct1ms316 KiB
40Accepted1ms316 KiB
41Partially correct1ms316 KiB
42Partially correct1ms500 KiB
43Accepted1ms316 KiB
44Partially correct1ms316 KiB
45Accepted1ms316 KiB
46Accepted1ms424 KiB
47Wrong answer1ms316 KiB
48Accepted1ms316 KiB
49Accepted1ms564 KiB
subtask40/16
50Accepted1ms316 KiB
51Accepted1ms316 KiB
52Partially correct1ms316 KiB
53Accepted1ms316 KiB
54Accepted1ms316 KiB
55Accepted1ms316 KiB
56Wrong answer1ms316 KiB
57Accepted1ms316 KiB
58Partially correct1ms420 KiB
59Partially correct1ms316 KiB
60Accepted1ms316 KiB
61Partially correct1ms316 KiB
62Accepted1ms316 KiB
63Accepted1ms564 KiB
64Partially correct1ms316 KiB
65Partially correct1ms316 KiB
66Partially correct1ms420 KiB
67Partially correct1ms508 KiB
68Partially correct1ms316 KiB
69Accepted1ms316 KiB
70Partially correct1ms316 KiB
71Partially correct1ms316 KiB
72Partially correct1ms344 KiB
73Partially correct1ms316 KiB
74Wrong answer1ms564 KiB
75Partially correct1ms500 KiB
76Accepted1ms316 KiB
77Accepted1ms316 KiB
78Wrong answer1ms372 KiB
79Accepted1ms532 KiB
80Partially correct1ms316 KiB
81Partially correct1ms316 KiB
82Partially correct1ms316 KiB
83Accepted1ms316 KiB
84Partially correct1ms316 KiB
85Partially correct1ms500 KiB
86Accepted1ms316 KiB
87Partially correct1ms316 KiB
88Accepted1ms316 KiB
89Accepted1ms424 KiB
90Wrong answer1ms316 KiB
91Accepted1ms316 KiB
92Accepted1ms564 KiB
subtask50/60
93Accepted1ms316 KiB
94Partially correct26ms2716 KiB
95Accepted1ms316 KiB
96Partially correct1ms316 KiB
97Accepted1ms316 KiB
98Accepted1ms316 KiB
99Accepted1ms316 KiB
100Wrong answer1ms316 KiB
101Accepted1ms316 KiB
102Partially correct1ms420 KiB
103Partially correct1ms316 KiB
104Accepted1ms316 KiB
105Partially correct1ms316 KiB
106Accepted1ms316 KiB
107Accepted1ms564 KiB
108Partially correct1ms316 KiB
109Partially correct1ms316 KiB
110Partially correct1ms420 KiB
111Partially correct1ms508 KiB
112Partially correct1ms316 KiB
113Accepted1ms316 KiB
114Partially correct1ms316 KiB
115Partially correct1ms316 KiB
116Partially correct1ms344 KiB
117Partially correct1ms316 KiB
118Wrong answer1ms564 KiB
119Partially correct1ms500 KiB
120Accepted1ms316 KiB
121Accepted1ms316 KiB
122Wrong answer1ms372 KiB
123Accepted1ms532 KiB
124Accepted28ms3556 KiB
125Accepted28ms3668 KiB
126Accepted28ms3636 KiB
127Partially correct27ms3544 KiB
128Accepted28ms3636 KiB
129Wrong answer28ms3544 KiB
130Wrong answer28ms3756 KiB
131Partially correct27ms3636 KiB
132Partially correct29ms3692 KiB
133Partially correct1ms316 KiB
134Partially correct1ms316 KiB
135Partially correct1ms316 KiB
136Accepted1ms316 KiB
137Partially correct1ms316 KiB
138Partially correct1ms500 KiB
139Accepted1ms316 KiB
140Partially correct1ms316 KiB
141Accepted1ms316 KiB
142Accepted1ms424 KiB
143Wrong answer1ms316 KiB
144Partially correct17ms2868 KiB
145Accepted14ms2636 KiB
146Wrong answer17ms3156 KiB
147Partially correct10ms1856 KiB
148Partially correct17ms3000 KiB
149Partially correct17ms2948 KiB
150Accepted1ms316 KiB
151Accepted1ms564 KiB
152Accepted16ms2976 KiB