108032024-04-14 13:12:06AblablablaMetróutasokcpp17Részben helyes 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();
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1748 KiB
2Részben helyes85ms3264 KiB
subtask23/12
3Elfogadva3ms2244 KiB
4Elfogadva3ms2340 KiB
5Elfogadva3ms2544 KiB
6Elfogadva3ms2796 KiB
7Elfogadva3ms2852 KiB
8Elfogadva3ms2968 KiB
9Elfogadva3ms3188 KiB
10Elfogadva3ms3272 KiB
11Részben helyes3ms3396 KiB
12Elfogadva3ms3480 KiB
13Elfogadva3ms3484 KiB
14Részben helyes3ms3720 KiB
15Elfogadva3ms3868 KiB
16Elfogadva3ms3880 KiB
subtask33/12
17Elfogadva3ms2244 KiB
18Elfogadva3ms2340 KiB
19Elfogadva3ms2544 KiB
20Elfogadva3ms2796 KiB
21Elfogadva3ms2852 KiB
22Elfogadva3ms2968 KiB
23Elfogadva3ms3188 KiB
24Elfogadva3ms3272 KiB
25Részben helyes3ms3396 KiB
26Elfogadva3ms3480 KiB
27Elfogadva3ms3892 KiB
28Elfogadva3ms3892 KiB
29Elfogadva3ms3892 KiB
30Elfogadva3ms4040 KiB
31Elfogadva3ms4036 KiB
32Elfogadva3ms4152 KiB
33Elfogadva3ms4148 KiB
34Elfogadva3ms4152 KiB
35Elfogadva3ms4100 KiB
36Elfogadva3ms4212 KiB
37Elfogadva3ms3484 KiB
38Részben helyes3ms3720 KiB
39Részben helyes3ms4216 KiB
40Részben helyes3ms4212 KiB
41Részben helyes3ms4344 KiB
42Részben helyes3ms4432 KiB
43Elfogadva3ms3868 KiB
44Elfogadva3ms3880 KiB
45Részben helyes3ms4424 KiB
46Részben helyes3ms4428 KiB
47Részben helyes3ms4540 KiB
48Elfogadva3ms4564 KiB
49Részben helyes3ms4332 KiB
subtask44/16
50Elfogadva3ms2244 KiB
51Elfogadva3ms2340 KiB
52Elfogadva3ms2544 KiB
53Elfogadva3ms2796 KiB
54Elfogadva3ms2852 KiB
55Elfogadva3ms2968 KiB
56Elfogadva3ms3188 KiB
57Elfogadva3ms3272 KiB
58Részben helyes3ms3396 KiB
59Elfogadva3ms3480 KiB
60Elfogadva3ms3892 KiB
61Elfogadva3ms3892 KiB
62Elfogadva3ms3892 KiB
63Elfogadva3ms4040 KiB
64Elfogadva3ms4036 KiB
65Elfogadva3ms4152 KiB
66Elfogadva3ms4148 KiB
67Elfogadva3ms4152 KiB
68Elfogadva3ms4100 KiB
69Elfogadva3ms4212 KiB
70Részben helyes3ms4488 KiB
71Elfogadva3ms4508 KiB
72Elfogadva3ms4528 KiB
73Elfogadva3ms4488 KiB
74Elfogadva3ms4492 KiB
75Elfogadva3ms4680 KiB
76Elfogadva3ms4892 KiB
77Részben helyes3ms4948 KiB
78Elfogadva3ms4960 KiB
79Elfogadva3ms5068 KiB
80Elfogadva3ms3484 KiB
81Részben helyes3ms3720 KiB
82Részben helyes3ms4216 KiB
83Részben helyes3ms4212 KiB
84Részben helyes3ms4344 KiB
85Részben helyes3ms4432 KiB
86Elfogadva3ms3868 KiB
87Elfogadva3ms3880 KiB
88Részben helyes3ms4424 KiB
89Részben helyes3ms4428 KiB
90Részben helyes3ms4540 KiB
91Elfogadva3ms4564 KiB
92Részben helyes3ms4332 KiB
subtask515/60
93Elfogadva3ms2244 KiB
94Részben helyes85ms6456 KiB
95Elfogadva3ms2340 KiB
96Elfogadva3ms2544 KiB
97Elfogadva3ms2796 KiB
98Elfogadva3ms2852 KiB
99Elfogadva3ms2968 KiB
100Elfogadva3ms3188 KiB
101Elfogadva3ms3272 KiB
102Részben helyes3ms3396 KiB
103Elfogadva3ms3480 KiB
104Elfogadva3ms3892 KiB
105Elfogadva3ms3892 KiB
106Elfogadva3ms3892 KiB
107Elfogadva3ms4040 KiB
108Elfogadva3ms4036 KiB
109Elfogadva3ms4152 KiB
110Elfogadva3ms4148 KiB
111Elfogadva3ms4152 KiB
112Elfogadva3ms4100 KiB
113Elfogadva3ms4212 KiB
114Részben helyes3ms4488 KiB
115Elfogadva3ms4508 KiB
116Elfogadva3ms4528 KiB
117Elfogadva3ms4488 KiB
118Elfogadva3ms4492 KiB
119Elfogadva3ms4680 KiB
120Elfogadva3ms4892 KiB
121Részben helyes3ms4948 KiB
122Elfogadva3ms4960 KiB
123Elfogadva3ms5068 KiB
124Elfogadva65ms6304 KiB
125Elfogadva67ms6304 KiB
126Elfogadva70ms6304 KiB
127Elfogadva67ms6456 KiB
128Elfogadva68ms6308 KiB
129Részben helyes82ms6388 KiB
130Részben helyes70ms6308 KiB
131Elfogadva65ms6304 KiB
132Elfogadva83ms6308 KiB
133Elfogadva3ms3484 KiB
134Részben helyes3ms3720 KiB
135Részben helyes3ms4216 KiB
136Részben helyes3ms4212 KiB
137Részben helyes3ms4344 KiB
138Részben helyes3ms4432 KiB
139Elfogadva3ms3868 KiB
140Elfogadva3ms3880 KiB
141Részben helyes3ms4424 KiB
142Részben helyes3ms4428 KiB
143Részben helyes3ms4540 KiB
144Részben helyes35ms6176 KiB
145Részben helyes32ms6180 KiB
146Részben helyes37ms6388 KiB
147Elfogadva24ms5740 KiB
148Részben helyes35ms6180 KiB
149Részben helyes32ms6176 KiB
150Elfogadva3ms4564 KiB
151Részben helyes3ms4332 KiB
152Elfogadva32ms6212 KiB