10960 2024. 04. 20 19:18:44 k_balint Metróutasok cpp17 Elfogadva 100/100 63ms 8520 KiB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int c=2e5+5;

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

bool check(ll k){
    ll cur=0;
    for(int i=1;i<=n;i++){
        ll le=(cur+arr[i]-k+1)/2;
        if(le>min(arr[i],cur)) return 0;
        cur=cur+arr[i]-2*max(0ll,le);
    }
    return 1;
}

bool jo(ll k){
    bool res = check(k);
    reverse(arr+1,arr+n+1);
    res &= check(k);
    reverse(arr+1,arr+n+1);
    return res;
}

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(jo(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+=arr[i];
            maxi=sum;
        }
        else{
            maxi=max(suf[i+1],maxi);
            break;
        }
    }
    cout << maxi << endl;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 2180 KiB
2 Elfogadva 59ms 5448 KiB
subtask2 12/12
3 Elfogadva 3ms 2480 KiB
4 Elfogadva 3ms 2436 KiB
5 Elfogadva 3ms 2692 KiB
6 Elfogadva 3ms 2904 KiB
7 Elfogadva 3ms 2984 KiB
8 Elfogadva 3ms 3120 KiB
9 Elfogadva 3ms 3332 KiB
10 Elfogadva 3ms 3408 KiB
11 Elfogadva 3ms 3376 KiB
12 Elfogadva 3ms 3452 KiB
13 Elfogadva 3ms 3592 KiB
14 Elfogadva 3ms 3596 KiB
15 Elfogadva 3ms 3820 KiB
16 Elfogadva 3ms 4020 KiB
subtask3 12/12
17 Elfogadva 3ms 2480 KiB
18 Elfogadva 3ms 2436 KiB
19 Elfogadva 3ms 2692 KiB
20 Elfogadva 3ms 2904 KiB
21 Elfogadva 3ms 2984 KiB
22 Elfogadva 3ms 3120 KiB
23 Elfogadva 3ms 3332 KiB
24 Elfogadva 3ms 3408 KiB
25 Elfogadva 3ms 3376 KiB
26 Elfogadva 3ms 3452 KiB
27 Elfogadva 3ms 3956 KiB
28 Elfogadva 3ms 3928 KiB
29 Elfogadva 3ms 3808 KiB
30 Elfogadva 3ms 3804 KiB
31 Elfogadva 3ms 4016 KiB
32 Elfogadva 3ms 4212 KiB
33 Elfogadva 3ms 4292 KiB
34 Elfogadva 3ms 4296 KiB
35 Elfogadva 3ms 4220 KiB
36 Elfogadva 3ms 4140 KiB
37 Elfogadva 3ms 3592 KiB
38 Elfogadva 3ms 3596 KiB
39 Elfogadva 3ms 4228 KiB
40 Elfogadva 3ms 4136 KiB
41 Elfogadva 3ms 4228 KiB
42 Elfogadva 3ms 4144 KiB
43 Elfogadva 3ms 3820 KiB
44 Elfogadva 3ms 4020 KiB
45 Elfogadva 3ms 4140 KiB
46 Elfogadva 3ms 4136 KiB
47 Elfogadva 3ms 4464 KiB
48 Elfogadva 3ms 4560 KiB
49 Elfogadva 3ms 4652 KiB
subtask4 16/16
50 Elfogadva 3ms 2480 KiB
51 Elfogadva 3ms 2436 KiB
52 Elfogadva 3ms 2692 KiB
53 Elfogadva 3ms 2904 KiB
54 Elfogadva 3ms 2984 KiB
55 Elfogadva 3ms 3120 KiB
56 Elfogadva 3ms 3332 KiB
57 Elfogadva 3ms 3408 KiB
58 Elfogadva 3ms 3376 KiB
59 Elfogadva 3ms 3452 KiB
60 Elfogadva 3ms 3956 KiB
61 Elfogadva 3ms 3928 KiB
62 Elfogadva 3ms 3808 KiB
63 Elfogadva 3ms 3804 KiB
64 Elfogadva 3ms 4016 KiB
65 Elfogadva 3ms 4212 KiB
66 Elfogadva 3ms 4292 KiB
67 Elfogadva 3ms 4296 KiB
68 Elfogadva 3ms 4220 KiB
69 Elfogadva 3ms 4140 KiB
70 Elfogadva 3ms 4888 KiB
71 Elfogadva 3ms 4980 KiB
72 Elfogadva 3ms 4936 KiB
73 Elfogadva 3ms 4988 KiB
74 Elfogadva 3ms 4992 KiB
75 Elfogadva 3ms 4940 KiB
76 Elfogadva 3ms 4948 KiB
77 Elfogadva 3ms 5016 KiB
78 Elfogadva 3ms 5272 KiB
79 Elfogadva 3ms 5152 KiB
80 Elfogadva 3ms 3592 KiB
81 Elfogadva 3ms 3596 KiB
82 Elfogadva 3ms 4228 KiB
83 Elfogadva 3ms 4136 KiB
84 Elfogadva 3ms 4228 KiB
85 Elfogadva 3ms 4144 KiB
86 Elfogadva 3ms 3820 KiB
87 Elfogadva 3ms 4020 KiB
88 Elfogadva 3ms 4140 KiB
89 Elfogadva 3ms 4136 KiB
90 Elfogadva 3ms 4464 KiB
91 Elfogadva 3ms 4560 KiB
92 Elfogadva 3ms 4652 KiB
subtask5 60/60
93 Elfogadva 3ms 2480 KiB
94 Elfogadva 59ms 8412 KiB
95 Elfogadva 3ms 2436 KiB
96 Elfogadva 3ms 2692 KiB
97 Elfogadva 3ms 2904 KiB
98 Elfogadva 3ms 2984 KiB
99 Elfogadva 3ms 3120 KiB
100 Elfogadva 3ms 3332 KiB
101 Elfogadva 3ms 3408 KiB
102 Elfogadva 3ms 3376 KiB
103 Elfogadva 3ms 3452 KiB
104 Elfogadva 3ms 3956 KiB
105 Elfogadva 3ms 3928 KiB
106 Elfogadva 3ms 3808 KiB
107 Elfogadva 3ms 3804 KiB
108 Elfogadva 3ms 4016 KiB
109 Elfogadva 3ms 4212 KiB
110 Elfogadva 3ms 4292 KiB
111 Elfogadva 3ms 4296 KiB
112 Elfogadva 3ms 4220 KiB
113 Elfogadva 3ms 4140 KiB
114 Elfogadva 3ms 4888 KiB
115 Elfogadva 3ms 4980 KiB
116 Elfogadva 3ms 4936 KiB
117 Elfogadva 3ms 4988 KiB
118 Elfogadva 3ms 4992 KiB
119 Elfogadva 3ms 4940 KiB
120 Elfogadva 3ms 4948 KiB
121 Elfogadva 3ms 5016 KiB
122 Elfogadva 3ms 5272 KiB
123 Elfogadva 3ms 5152 KiB
124 Elfogadva 59ms 8368 KiB
125 Elfogadva 59ms 8520 KiB
126 Elfogadva 61ms 8488 KiB
127 Elfogadva 57ms 8368 KiB
128 Elfogadva 63ms 8372 KiB
129 Elfogadva 61ms 8416 KiB
130 Elfogadva 59ms 8452 KiB
131 Elfogadva 57ms 8456 KiB
132 Elfogadva 59ms 8460 KiB
133 Elfogadva 3ms 3592 KiB
134 Elfogadva 3ms 3596 KiB
135 Elfogadva 3ms 4228 KiB
136 Elfogadva 3ms 4136 KiB
137 Elfogadva 3ms 4228 KiB
138 Elfogadva 3ms 4144 KiB
139 Elfogadva 3ms 3820 KiB
140 Elfogadva 3ms 4020 KiB
141 Elfogadva 3ms 4140 KiB
142 Elfogadva 3ms 4136 KiB
143 Elfogadva 3ms 4464 KiB
144 Elfogadva 52ms 8148 KiB
145 Elfogadva 46ms 7864 KiB
146 Elfogadva 54ms 8304 KiB
147 Elfogadva 32ms 7040 KiB
148 Elfogadva 54ms 8260 KiB
149 Elfogadva 50ms 8208 KiB
150 Elfogadva 3ms 4560 KiB
151 Elfogadva 3ms 4652 KiB
152 Elfogadva 50ms 8096 KiB