Task: | Metsämetro |
Sender: | siirikuoppala |
Submission time: | 2018-01-18 16:39:35 +0200 |
Language: | C++ |
Status: | READY |
Result: | 42 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 14 |
#2 | ACCEPTED | 28 |
#3 | WRONG ANSWER | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.06 s | 1 | details |
#2 | ACCEPTED | 0.06 s | 1 | details |
#3 | ACCEPTED | 0.08 s | 1 | details |
#4 | ACCEPTED | 0.05 s | 1 | details |
#5 | ACCEPTED | 0.07 s | 1 | details |
#6 | ACCEPTED | 0.06 s | 1 | details |
#7 | ACCEPTED | 0.06 s | 1 | details |
#8 | ACCEPTED | 0.07 s | 1 | details |
#9 | ACCEPTED | 0.07 s | 1 | details |
#10 | ACCEPTED | 0.06 s | 1 | details |
#11 | ACCEPTED | 0.07 s | 2 | details |
#12 | ACCEPTED | 0.07 s | 2 | details |
#13 | ACCEPTED | 0.07 s | 2 | details |
#14 | ACCEPTED | 0.06 s | 2 | details |
#15 | ACCEPTED | 0.07 s | 2 | details |
#16 | ACCEPTED | 0.07 s | 2 | details |
#17 | ACCEPTED | 0.06 s | 2 | details |
#18 | ACCEPTED | 0.06 s | 2 | details |
#19 | ACCEPTED | 0.07 s | 2 | details |
#20 | ACCEPTED | 0.05 s | 2 | details |
#21 | WRONG ANSWER | 0.15 s | 3 | details |
#22 | WRONG ANSWER | 0.16 s | 3 | details |
#23 | WRONG ANSWER | 0.15 s | 3 | details |
#24 | WRONG ANSWER | 0.13 s | 3 | details |
#25 | WRONG ANSWER | 0.15 s | 3 | details |
#26 | WRONG ANSWER | 0.13 s | 3 | details |
#27 | WRONG ANSWER | 0.17 s | 3 | details |
#28 | WRONG ANSWER | 0.15 s | 3 | details |
#29 | WRONG ANSWER | 0.16 s | 3 | details |
#30 | WRONG ANSWER | 0.16 s | 3 | details |
Code
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define N (1<<20) ll t[N], V1[N], V2[N]; vector<int> v[N]; int V = 0; bool ok(int Vmax, int n){ int a=0, b=0; for(int i=1; i<=n; ++i){ int x = t[i]; int ea = a; if(a >= x) a = a-x; else if(b>=x) a = (a+x) % 2; else a = x-b; if(b+x <= Vmax) b+=x; else{ int d = Vmax-ea; if(ea+x <= Vmax) b = Vmax - (d+x)%2; else if(x-b <= Vmax) b = Vmax - (d+x)%2; else return 0; } } if(a == 0) return 1; else return 0; } int main(){ int n; cin >> n; ll s = 0; for(int i=1; i<=n; ++i) { cin >> t[i]; s += t[i]; } ll V=0, Vmax=0; for(int i=1; i<=n; ++i){ ll x = t[i]; V2[i] = V2[i-1] + x; } for(int i=n; i>0; --i){ ll x = t[i]; Vmax += x; V2[i-1] = min(V2[i-1], Vmax); V = max(V, V2[i-1]); } Vmax = V; V = 0; for(ll b = Vmax; b>=1; b/=2){ while(!ok(V+b, n)) V+=b; } cout << V+1 << " " << Vmax << "\n"; }
Test details
Test 1
Group: 1
Verdict: ACCEPTED
input |
---|
10 9 4 9 7 6 10 4 6 2 9 |
correct output |
---|
9 31 |
user output |
---|
9 31 |
Test 2
Group: 1
Verdict: ACCEPTED
input |
---|
10 5 6 3 5 6 3 4 7 1 10 |
correct output |
---|
10 25 |
user output |
---|
10 25 |
Test 3
Group: 1
Verdict: ACCEPTED
input |
---|
10 10 2 4 1 4 9 6 3 5 10 |
correct output |
---|
10 24 |
user output |
---|
10 24 |
Test 4
Group: 1
Verdict: ACCEPTED
input |
---|
10 7 5 1 3 8 4 5 4 6 3 |
correct output |
---|
7 22 |
user output |
---|
7 22 |
Test 5
Group: 1
Verdict: ACCEPTED
input |
---|
10 10 7 8 4 10 6 8 6 2 3 |
correct output |
---|
10 29 |
user output |
---|
10 29 |
Test 6
Group: 1
Verdict: ACCEPTED
input |
---|
10 1 2 8 2 3 1 3 1 4 9 |
correct output |
---|
9 17 |
user output |
---|
9 17 |
Test 7
Group: 1
Verdict: ACCEPTED
input |
---|
10 2 8 2 5 8 8 5 10 9 7 |
correct output |
---|
7 31 |
user output |
---|
7 31 |
Test 8
Group: 1
Verdict: ACCEPTED
input |
---|
10 2 10 4 8 10 10 9 3 9 7 |
correct output |
---|
8 34 |
user output |
---|
8 34 |
Test 9
Group: 1
Verdict: ACCEPTED
input |
---|
10 10 7 9 1 7 8 4 4 1 5 |
correct output |
---|
10 27 |
user output |
---|
10 27 |
Test 10
Group: 1
Verdict: ACCEPTED
input |
---|
10 1 4 7 7 3 1 10 6 4 3 |
correct output |
---|
5 23 |
user output |
---|
5 23 |
Test 11
Group: 2
Verdict: ACCEPTED
input |
---|
100 5 3 4 7 5 1 7 1 6 10 2 9 6 5 9... |
correct output |
---|
6 281 |
user output |
---|
6 281 |
Test 12
Group: 2
Verdict: ACCEPTED
input |
---|
100 3 9 7 3 6 6 4 3 1 8 2 4 2 6 2 ... |
correct output |
---|
7 252 |
user output |
---|
7 252 |
Test 13
Group: 2
Verdict: ACCEPTED
input |
---|
100 8 2 3 4 8 3 2 7 10 10 3 2 3 4 ... |
correct output |
---|
8 252 |
user output |
---|
8 252 |
Test 14
Group: 2
Verdict: ACCEPTED
input |
---|
100 4 4 9 8 5 6 2 3 7 10 10 2 7 5 ... |
correct output |
---|
9 261 |
user output |
---|
9 261 |
Test 15
Group: 2
Verdict: ACCEPTED
input |
---|
100 7 3 3 5 10 6 6 8 10 5 5 8 3 5 ... |
correct output |
---|
10 300 |
user output |
---|
10 300 |
Test 16
Group: 2
Verdict: ACCEPTED
input |
---|
100 9 5 2 1 9 8 6 4 1 6 3 5 3 1 4 ... |
correct output |
---|
9 289 |
user output |
---|
9 289 |
Test 17
Group: 2
Verdict: ACCEPTED
input |
---|
100 9 7 5 5 4 1 9 2 3 5 10 2 10 5 ... |
correct output |
---|
9 287 |
user output |
---|
9 287 |
Test 18
Group: 2
Verdict: ACCEPTED
input |
---|
100 3 8 5 10 8 10 9 2 8 3 1 2 9 7 ... |
correct output |
---|
6 282 |
user output |
---|
6 282 |
Test 19
Group: 2
Verdict: ACCEPTED
input |
---|
100 6 3 9 2 8 7 8 4 6 4 4 10 2 10 ... |
correct output |
---|
8 260 |
user output |
---|
8 260 |
Test 20
Group: 2
Verdict: ACCEPTED
input |
---|
100 10 8 7 8 10 3 1 2 1 1 7 4 5 5 ... |
correct output |
---|
10 279 |
user output |
---|
10 279 |
Test 21
Group: 3
Verdict: WRONG ANSWER
input |
---|
100000 917855934 394938644 81692499 4... |
correct output |
---|
917855934 23490295363738 |
user output |
---|
22755654590142 23490295363738 |
Test 22
Group: 3
Verdict: WRONG ANSWER
input |
---|
100000 898177957 193852227 11785863 3... |
correct output |
---|
898177957 23488890808371 |
user output |
---|
258377540770725 23488890808371 |
Test 23
Group: 3
Verdict: WRONG ANSWER
input |
---|
100000 560743028 996665755 25721760 4... |
correct output |
---|
576170439 23599624330076 |
user output |
---|
64898601974892 23599624330076 |
Test 24
Group: 3
Verdict: WRONG ANSWER
input |
---|
100000 836491959 800539061 666447484 ... |
correct output |
---|
836491959 23450143338851 |
user output |
---|
193463343372983 23450143338851 |
Test 25
Group: 3
Verdict: WRONG ANSWER
input |
---|
100000 156445358 170997055 927078622 ... |
correct output |
---|
930838017 23503313036290 |
user output |
---|
17442793027073 23503313036290 |
Test 26
Group: 3
Verdict: WRONG ANSWER
input |
---|
100000 869942654 614144284 154904581 ... |
correct output |
---|
869942654 23544105883410 |
user output |
---|
55917049169278 23544105883410 |
Test 27
Group: 3
Verdict: WRONG ANSWER
input |
---|
100000 471025024 244072220 419574192 ... |
correct output |
---|
657776925 23597080152723 |
user output |
---|
34656748888349 23597080152723 |
Test 28
Group: 3
Verdict: WRONG ANSWER
input |
---|
100000 561299091 285120535 109702008 ... |
correct output |
---|
862325964 23517085653307 |
user output |
---|
398320424324300 23517085653307 |
Test 29
Group: 3
Verdict: WRONG ANSWER
input |
---|
100000 356879006 3017698 603259365 18... |
correct output |
---|
499995467 23540251578008 |
user output |
---|
135171710735179 23540251578008 |
Test 30
Group: 3
Verdict: WRONG ANSWER
input |
---|
100000 190109479 83895435 595795373 8... |
correct output |
---|
598676555 23565408317817 |
user output |
---|
67749412803659 23565408317817 |