QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #4527 | #427. 序列 | Qingyu | 100 ✓ | 52ms | 3576kb | C++11 | 1.5kb | 2020-07-02 17:57:36 | 2021-12-19 05:22:12 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
typedef long long ll;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); }
template <typename T> void read(T &x) {
x = 0; int f = 1;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
x *= f;
}
int main() {
int T; read(T);
while (T--) {
int n; read(n); ll ans = 0;
int com = 0; pair <int, int> cur = make_pair(0, 0), nxt = make_pair(0, 0);
for (int i = 1; i <= n; i++, swap(cur, nxt)) {
int now; read(now);
if (nxt.first != 0) {
if (com + cur.second >= now) {
int dec = com + cur.second - now;
cur.first += min(dec, com) + min(dec, cur.second) - dec;
com -= min(dec, com), cur.second -= min(dec, cur.second);
} else if (com + cur.second + nxt.first >= now) {
int dif = now - com - cur.second;
com += dif, nxt.first -= dif;
} else {
com += nxt.first, nxt.first = 0;
int dif = now - com - cur.second;
cur.first += dif, ans += dif;
}
} else {
if (com + cur.second >= now) {
int dec = com + cur.second - now;
cur.first += min(dec, com) + min(dec, cur.second) - dec;
com -= min(dec, com), cur.second -= min(dec, cur.second);
} else {
int inc = now - (com + cur.second);
cur.first += inc, ans += inc;
}
}
nxt.second += nxt.first;
nxt.first = 0;
}
cout << ans << endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 1ms
memory: 3488kb
input:
10 5 1 10 7 8 5 5 2 2 7 2 7 5 10 3 3 5 0 5 3 4 2 7 2 5 1 6 8 9 5 5 5 4 4 2 5 5 5 1 1 8 2 5 1 2 8 6 5 5 3 0 2 3 1 5 6 7 5 9 4
output:
10 7 12 8 9 7 12 8 6 10
result:
ok 10 lines
Test #2:
score: 10
Accepted
time: 2ms
memory: 3504kb
input:
10 50 25 24 28 15 45 2 40 25 23 32 38 49 7 33 34 9 10 37 49 20 19 38 19 22 43 48 26 49 26 34 15 50 18 17 8 3 5 23 5 14 4 42 24 22 11 43 4 36 39 14 50 45 1 49 43 43 46 1 18 39 23 3 30 41 10 3 3 34 1 33 3 27 41 1 36 36 0 20 18 15 26 1 27 10 34 22 13 2 25 4 24 7 50 10 43 0 3 38 11 32 33 50 14 37 39 50 45 19 40 35 42 50 1 16 32 7 33 29 45 3 16 10 8 35 10 18 17 9 7 32 33 42 45 3 12 4 43 0 13 29 31 40 21 39 33 1 10 37 39 14 5 49 50 37 33 24 42 40 16 9 21 49 1 41 17 40 24 28 34 8 2 28 50 10 31 14 22 45...
output:
341 417 371 342 357 321 309 340 305 324
result:
ok 10 lines
Test #3:
score: 10
Accepted
time: 0ms
memory: 3504kb
input:
10 50 37 8 12 4 49 42 44 35 45 20 28 13 13 45 48 21 27 35 8 39 49 18 5 6 12 12 31 26 16 40 36 27 10 35 31 25 10 4 11 12 0 4 5 23 45 1 20 28 13 14 50 11 3 20 19 20 47 35 15 43 34 15 38 22 47 5 12 37 0 10 47 23 33 25 25 2 47 8 30 7 32 45 0 38 32 45 4 29 38 31 22 19 40 22 6 30 3 6 21 2 50 50 12 49 44 5 7 12 4 16 43 27 12 25 42 0 9 25 9 6 22 17 47 38 50 20 8 5 9 19 44 3 14 24 13 42 47 25 19 45 9 18 17 10 36 26 41 15 4 46 6 16 50 23 40 27 6 43 15 28 27 20 41 11 7 29 44 36 38 47 37 49 33 49 8 47 42 24...
output:
314 390 366 350 390 293 408 442 333 323
result:
ok 10 lines
Test #4:
score: 10
Accepted
time: 2ms
memory: 3448kb
input:
10 200 180 105 5 152 124 95 115 168 61 91 66 92 160 125 65 44 128 39 69 43 32 134 144 10 18 81 10 161 113 169 13 60 31 164 148 93 4 96 85 114 67 177 178 173 9 124 163 74 20 6 121 20 74 166 143 133 113 139 10 31 128 46 33 192 108 57 178 131 97 160 86 60 40 106 70 0 125 37 90 152 108 106 62 173 190 25 4 174 46 82 137 87 93 157 127 102 19 172 72 122 186 137 95 95 145 145 59 171 3 141 5 21 137 40 137 104 60 165 197 171 72 27 53 146 11 75 12 164 52 165 55 127 37 176 146 117 139 165 30 46 181 178 26 3...
output:
5786 5845 4942 5243 4875 4472 5569 5505 5291 5985
result:
ok 10 lines
Test #5:
score: 10
Accepted
time: 3ms
memory: 3492kb
input:
10 200 13 169 101 137 5 66 83 119 26 196 173 91 100 108 94 141 109 105 4 144 128 168 39 41 11 8 11 121 96 158 10 7 133 120 33 129 178 168 200 166 14 96 21 53 82 115 99 67 198 56 24 10 33 135 38 56 117 146 145 135 112 198 170 191 124 145 150 167 107 72 113 137 5 62 122 29 116 29 169 128 28 116 125 58 89 67 179 90 121 116 138 184 19 113 93 185 168 20 7 154 79 78 167 132 117 159 21 40 170 130 106 95 160 115 23 15 25 76 135 66 187 80 21 26 75 123 39 61 181 194 151 59 92 84 187 200 52 38 2 177 105 79...
output:
4937 5410 5354 4816 5650 5106 5161 5586 4864 5350
result:
ok 10 lines
Test #6:
score: 10
Accepted
time: 2ms
memory: 3576kb
input:
10 200 474241179 824759444 179897408 58543033 31219226 992918564 586279732 745512362 694893964 271873492 677197939 726776376 847464287 86622849 549167172 374838617 250574641 70790981 173344739 936000682 906357546 101457135 916382647 15826598 31323108 890116978 879804005 663739122 405558169 523052230 33388541 191731755 178649122 187722830 187313679 969195080 766516889 511465319 849523551 172459155 345180629 968149879 326376824 562538681 544209292 964057397 992135409 722583689 282170030 82783141 4...
output:
27149795167 26148727940 26657484986 28158059012 28395912986 25674071785 27037638566 26893405040 26976445221 27115391316
result:
ok 10 lines
Test #7:
score: 10
Accepted
time: 3ms
memory: 3392kb
input:
10 1000 144351583 427808372 841332406 915042334 791881292 121459161 206543816 442016184 648630707 22844293 662475389 449451433 124399854 746991357 672974863 837034768 670357798 557319603 532613172 890926196 3785951 539326786 214237940 677853321 397141215 697387063 143226671 380329904 503382495 581095304 10831612 406666522 170730591 741204037 297332708 868858620 952323288 626009259 334326737 242174492 374378266 34275263 731746257 568259235 87235217 892101015 755466045 485908854 975777287 65160551...
output:
131580223531 133091338611 133276284628 129327529241 126624435850 127006306206 132543542806 129438528140 135842416361 125438351371
result:
ok 10 lines
Test #8:
score: 10
Accepted
time: 11ms
memory: 3340kb
input:
10 10000 134528114 757277876 488671939 294865299 146085056 337058121 89424776 790702183 406201207 393774627 395342526 580057960 750924565 179044376 743848556 614982465 180343233 368251400 621103535 20052648 880689403 543904645 553789869 999554838 262332413 504818531 564886153 371494125 859477682 775829628 263742679 914567309 24871352 350051097 567060460 144104951 838731570 817912087 472287623 498559200 136933414 482219007 225094863 241754391 583868342 460089666 317577699 258216772 670512290 8194...
output:
1295832812264 1285008354812 1271754417664 1278371646136 1306392422562 1296376575571 1284140246537 1308925058551 1286308426452 1280308892116
result:
ok 10 lines
Test #9:
score: 10
Accepted
time: 12ms
memory: 3336kb
input:
10 10000 739801696 647485569 994894748 877842747 391687964 718068752 981359359 898151633 855874358 973821299 240488593 216013041 808751983 551019381 270550547 219735291 779811783 458416207 465567637 250276842 283194919 985677626 780226733 294065751 742485325 946238295 478132811 939912689 223080452 219128820 72994355 231503583 897984822 267880869 535857220 99500566 495438084 283218611 255239427 663035884 791274612 189986194 785767020 25880562 599289231 61036008 48635181 795399488 56709205 8229360...
output:
1295460152007 1278930025733 1286291384294 1283764398140 1287033111223 1298678827861 1292107371003 1288078509120 1276101012983 1277948652599
result:
ok 10 lines
Test #10:
score: 10
Accepted
time: 52ms
memory: 3496kb
input:
10 100000 630607255 461950434 120706961 486326610 202590109 968496359 374214488 838696181 683763082 426146834 707152820 674635530 723129820 338776480 786753996 485930718 271119036 795148496 988325677 832086919 362657498 68165453 395535090 155788206 851511578 817546215 702638021 503068098 751800844 443043981 728273144 194125717 759540133 163116 762010912 447832186 60239235 772157668 626031157 94343576 225878331 255216862 533102109 323109875 553444325 542697457 2420324 89278390 473580145 10856392 ...
output:
12854769460577 12879187620566 12903502337369 12907876797073 12858297018275 12912851305219 12861588234578 12879271004787 12857728357913 12882389664500
result:
ok 10 lines