108032024-04-14 13:12:06AblablablaMetróutasokcpp17Partially correct 25/10085ms6456 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();
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1748 KiB
2Partially correct85ms3264 KiB
subtask23/12
3Accepted3ms2244 KiB
4Accepted3ms2340 KiB
5Accepted3ms2544 KiB
6Accepted3ms2796 KiB
7Accepted3ms2852 KiB
8Accepted3ms2968 KiB
9Accepted3ms3188 KiB
10Accepted3ms3272 KiB
11Partially correct3ms3396 KiB
12Accepted3ms3480 KiB
13Accepted3ms3484 KiB
14Partially correct3ms3720 KiB
15Accepted3ms3868 KiB
16Accepted3ms3880 KiB
subtask33/12
17Accepted3ms2244 KiB
18Accepted3ms2340 KiB
19Accepted3ms2544 KiB
20Accepted3ms2796 KiB
21Accepted3ms2852 KiB
22Accepted3ms2968 KiB
23Accepted3ms3188 KiB
24Accepted3ms3272 KiB
25Partially correct3ms3396 KiB
26Accepted3ms3480 KiB
27Accepted3ms3892 KiB
28Accepted3ms3892 KiB
29Accepted3ms3892 KiB
30Accepted3ms4040 KiB
31Accepted3ms4036 KiB
32Accepted3ms4152 KiB
33Accepted3ms4148 KiB
34Accepted3ms4152 KiB
35Accepted3ms4100 KiB
36Accepted3ms4212 KiB
37Accepted3ms3484 KiB
38Partially correct3ms3720 KiB
39Partially correct3ms4216 KiB
40Partially correct3ms4212 KiB
41Partially correct3ms4344 KiB
42Partially correct3ms4432 KiB
43Accepted3ms3868 KiB
44Accepted3ms3880 KiB
45Partially correct3ms4424 KiB
46Partially correct3ms4428 KiB
47Partially correct3ms4540 KiB
48Accepted3ms4564 KiB
49Partially correct3ms4332 KiB
subtask44/16
50Accepted3ms2244 KiB
51Accepted3ms2340 KiB
52Accepted3ms2544 KiB
53Accepted3ms2796 KiB
54Accepted3ms2852 KiB
55Accepted3ms2968 KiB
56Accepted3ms3188 KiB
57Accepted3ms3272 KiB
58Partially correct3ms3396 KiB
59Accepted3ms3480 KiB
60Accepted3ms3892 KiB
61Accepted3ms3892 KiB
62Accepted3ms3892 KiB
63Accepted3ms4040 KiB
64Accepted3ms4036 KiB
65Accepted3ms4152 KiB
66Accepted3ms4148 KiB
67Accepted3ms4152 KiB
68Accepted3ms4100 KiB
69Accepted3ms4212 KiB
70Partially correct3ms4488 KiB
71Accepted3ms4508 KiB
72Accepted3ms4528 KiB
73Accepted3ms4488 KiB
74Accepted3ms4492 KiB
75Accepted3ms4680 KiB
76Accepted3ms4892 KiB
77Partially correct3ms4948 KiB
78Accepted3ms4960 KiB
79Accepted3ms5068 KiB
80Accepted3ms3484 KiB
81Partially correct3ms3720 KiB
82Partially correct3ms4216 KiB
83Partially correct3ms4212 KiB
84Partially correct3ms4344 KiB
85Partially correct3ms4432 KiB
86Accepted3ms3868 KiB
87Accepted3ms3880 KiB
88Partially correct3ms4424 KiB
89Partially correct3ms4428 KiB
90Partially correct3ms4540 KiB
91Accepted3ms4564 KiB
92Partially correct3ms4332 KiB
subtask515/60
93Accepted3ms2244 KiB
94Partially correct85ms6456 KiB
95Accepted3ms2340 KiB
96Accepted3ms2544 KiB
97Accepted3ms2796 KiB
98Accepted3ms2852 KiB
99Accepted3ms2968 KiB
100Accepted3ms3188 KiB
101Accepted3ms3272 KiB
102Partially correct3ms3396 KiB
103Accepted3ms3480 KiB
104Accepted3ms3892 KiB
105Accepted3ms3892 KiB
106Accepted3ms3892 KiB
107Accepted3ms4040 KiB
108Accepted3ms4036 KiB
109Accepted3ms4152 KiB
110Accepted3ms4148 KiB
111Accepted3ms4152 KiB
112Accepted3ms4100 KiB
113Accepted3ms4212 KiB
114Partially correct3ms4488 KiB
115Accepted3ms4508 KiB
116Accepted3ms4528 KiB
117Accepted3ms4488 KiB
118Accepted3ms4492 KiB
119Accepted3ms4680 KiB
120Accepted3ms4892 KiB
121Partially correct3ms4948 KiB
122Accepted3ms4960 KiB
123Accepted3ms5068 KiB
124Accepted65ms6304 KiB
125Accepted67ms6304 KiB
126Accepted70ms6304 KiB
127Accepted67ms6456 KiB
128Accepted68ms6308 KiB
129Partially correct82ms6388 KiB
130Partially correct70ms6308 KiB
131Accepted65ms6304 KiB
132Accepted83ms6308 KiB
133Accepted3ms3484 KiB
134Partially correct3ms3720 KiB
135Partially correct3ms4216 KiB
136Partially correct3ms4212 KiB
137Partially correct3ms4344 KiB
138Partially correct3ms4432 KiB
139Accepted3ms3868 KiB
140Accepted3ms3880 KiB
141Partially correct3ms4424 KiB
142Partially correct3ms4428 KiB
143Partially correct3ms4540 KiB
144Partially correct35ms6176 KiB
145Partially correct32ms6180 KiB
146Partially correct37ms6388 KiB
147Accepted24ms5740 KiB
148Partially correct35ms6180 KiB
149Partially correct32ms6176 KiB
150Accepted3ms4564 KiB
151Partially correct3ms4332 KiB
152Accepted32ms6212 KiB