109442024-04-20 18:02:38k_balintMetróutasokcpp17Wrong answer 0/10030ms7484 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int c=2e5+5;

int n;
int arr[c];
ll suf[c];

bool check(ll k){
    ll cur=0;
    for(int i=1;i<=n;i++){
        if(arr[i]-cur>k) return 0;
        if(cur+arr[i]<=k) cur+=arr[i];
        else if( ((cur+arr[i])&1) == (k&1)) cur=k;
        else cur=k-1;
    }
    return 1;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }

    ll l=0,r=1e15;
    while(l<r-1){
        ll mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid;
    }
    cout << r << endl;

    for(int i=n;i>0;i--) suf[i]=suf[i+1]+arr[i];

    ll sum=0;
    ll maxi=0;
    for(int i=1;i<=n;i++){
        if(suf[i+1]>=sum+arr[i]){
            sum+=sum+arr[i];
            maxi=sum;
        }
        else{
            maxi=max(suf[i+1],maxi);
            break;
        }
    }
    cout << maxi << endl;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms2080 KiB
2Wrong answer28ms4660 KiB
subtask20/12
3Accepted3ms2348 KiB
4Accepted3ms2560 KiB
5Wrong answer3ms2768 KiB
6Accepted3ms3124 KiB
7Accepted3ms3320 KiB
8Accepted3ms3404 KiB
9Wrong answer3ms3324 KiB
10Partially correct3ms3364 KiB
11Partially correct3ms3452 KiB
12Partially correct3ms3664 KiB
13Partially correct3ms3748 KiB
14Partially correct3ms3672 KiB
15Accepted3ms3788 KiB
16Partially correct3ms4004 KiB
subtask30/12
17Accepted3ms2348 KiB
18Accepted3ms2560 KiB
19Wrong answer3ms2768 KiB
20Accepted3ms3124 KiB
21Accepted3ms3320 KiB
22Accepted3ms3404 KiB
23Wrong answer3ms3324 KiB
24Partially correct3ms3364 KiB
25Partially correct3ms3452 KiB
26Partially correct3ms3664 KiB
27Partially correct3ms4088 KiB
28Wrong answer3ms4088 KiB
29Partially correct3ms4180 KiB
30Partially correct3ms4088 KiB
31Partially correct3ms4084 KiB
32Wrong answer3ms4084 KiB
33Wrong answer3ms4092 KiB
34Partially correct3ms4236 KiB
35Partially correct3ms4088 KiB
36Partially correct3ms4216 KiB
37Partially correct3ms3748 KiB
38Partially correct3ms3672 KiB
39Wrong answer3ms4428 KiB
40Partially correct3ms4516 KiB
41Wrong answer3ms4588 KiB
42Partially correct3ms4520 KiB
43Accepted3ms3788 KiB
44Partially correct3ms4004 KiB
45Partially correct3ms4608 KiB
46Partially correct3ms4604 KiB
47Wrong answer3ms4612 KiB
48Partially correct3ms4836 KiB
49Accepted3ms4828 KiB
subtask40/16
50Accepted3ms2348 KiB
51Accepted3ms2560 KiB
52Wrong answer3ms2768 KiB
53Accepted3ms3124 KiB
54Accepted3ms3320 KiB
55Accepted3ms3404 KiB
56Wrong answer3ms3324 KiB
57Partially correct3ms3364 KiB
58Partially correct3ms3452 KiB
59Partially correct3ms3664 KiB
60Partially correct3ms4088 KiB
61Wrong answer3ms4088 KiB
62Partially correct3ms4180 KiB
63Partially correct3ms4088 KiB
64Partially correct3ms4084 KiB
65Wrong answer3ms4084 KiB
66Wrong answer3ms4092 KiB
67Partially correct3ms4236 KiB
68Partially correct3ms4088 KiB
69Partially correct3ms4216 KiB
70Partially correct3ms4744 KiB
71Wrong answer3ms4972 KiB
72Partially correct3ms4860 KiB
73Wrong answer3ms4744 KiB
74Wrong answer3ms4820 KiB
75Partially correct3ms4824 KiB
76Partially correct3ms4744 KiB
77Partially correct3ms4832 KiB
78Wrong answer3ms4952 KiB
79Partially correct3ms5036 KiB
80Partially correct3ms3748 KiB
81Partially correct3ms3672 KiB
82Wrong answer3ms4428 KiB
83Partially correct3ms4516 KiB
84Wrong answer3ms4588 KiB
85Partially correct3ms4520 KiB
86Accepted3ms3788 KiB
87Partially correct3ms4004 KiB
88Partially correct3ms4608 KiB
89Partially correct3ms4604 KiB
90Wrong answer3ms4612 KiB
91Partially correct3ms4836 KiB
92Accepted3ms4828 KiB
subtask50/60
93Accepted3ms2348 KiB
94Wrong answer28ms7352 KiB
95Accepted3ms2560 KiB
96Wrong answer3ms2768 KiB
97Accepted3ms3124 KiB
98Accepted3ms3320 KiB
99Accepted3ms3404 KiB
100Wrong answer3ms3324 KiB
101Partially correct3ms3364 KiB
102Partially correct3ms3452 KiB
103Partially correct3ms3664 KiB
104Partially correct3ms4088 KiB
105Wrong answer3ms4088 KiB
106Partially correct3ms4180 KiB
107Partially correct3ms4088 KiB
108Partially correct3ms4084 KiB
109Wrong answer3ms4084 KiB
110Wrong answer3ms4092 KiB
111Partially correct3ms4236 KiB
112Partially correct3ms4088 KiB
113Partially correct3ms4216 KiB
114Partially correct3ms4744 KiB
115Wrong answer3ms4972 KiB
116Partially correct3ms4860 KiB
117Wrong answer3ms4744 KiB
118Wrong answer3ms4820 KiB
119Partially correct3ms4824 KiB
120Partially correct3ms4744 KiB
121Partially correct3ms4832 KiB
122Wrong answer3ms4952 KiB
123Partially correct3ms5036 KiB
124Partially correct28ms7280 KiB
125Partially correct29ms7280 KiB
126Partially correct29ms7336 KiB
127Wrong answer28ms7332 KiB
128Partially correct30ms7280 KiB
129Wrong answer29ms7280 KiB
130Wrong answer29ms7280 KiB
131Partially correct28ms7428 KiB
132Wrong answer30ms7484 KiB
133Partially correct3ms3748 KiB
134Partially correct3ms3672 KiB
135Wrong answer3ms4428 KiB
136Partially correct3ms4516 KiB
137Wrong answer3ms4588 KiB
138Partially correct3ms4520 KiB
139Accepted3ms3788 KiB
140Partially correct3ms4004 KiB
141Partially correct3ms4608 KiB
142Partially correct3ms4604 KiB
143Wrong answer3ms4612 KiB
144Partially correct23ms7192 KiB
145Partially correct21ms6968 KiB
146Wrong answer25ms7352 KiB
147Partially correct16ms6368 KiB
148Wrong answer23ms7208 KiB
149Partially correct23ms7196 KiB
150Partially correct3ms4836 KiB
151Accepted3ms4828 KiB
152Partially correct21ms7084 KiB