QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#554273 | #8542. Add One 2 | ucup-team1231# | AC ✓ | 218ms | 28732kb | C++14 | 1.3kb | 2024-09-09 09:42:59 | 2024-09-09 09:42:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n;
LL y[1000005], ret;
vector<pair<LL, LL> > ans;
pair<LL, LL> tmerge(vector<pair<LL, LL> > vec) {
for(int i = 0; i + 1 < (int)vec.size(); i++) {
ans.push_back(make_pair(vec[i].second, vec[i + 1].first - vec[i].first));
vec[i + 1].second += vec[i].second;
}
return vec.back();
}
void solve() {
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%lld", &y[i]);
ans.clear();
ret = 0;
vector<pair<LL, LL> > sta;
for(int i = 0; i < n; i++) {
vector<pair<LL, LL> > vec;
while(!sta.empty() && sta.back().first <= y[i]) {
vec.push_back(sta.back()); sta.pop_back();
}
vec.push_back(make_pair(y[i], 1));
sta.push_back(tmerge(vec));
}
reverse(sta.begin(),sta.end());
tmerge(sta);
sort(ans.begin(), ans.end());
LL S = 0;
for(int i = 0; i + 1 < n; i++) S += abs(y[i + 1] - y[i]);
S -= y[0] + y[n - 1];
S = max(S, 0LL) / 2;
for(auto p : ans) {
LL d = min(p.second, S);
ret += p.first * d; S -= d;
}
for(int i = 0; i < n; i++) ret += y[i];
printf("%lld\n", ret);
}
int main() {
int T;
scanf("%d", &T);
while(T--) solve();
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 4024kb
input:
3 5 1 1 1 1 1 10 0 0 0 0 1000000000 0 0 0 0 0 13 1 1 4 5 1 4 1 9 1 9 8 1 0
output:
5 5000000000 76
result:
ok 3 number(s): "5 5000000000 76"
Test #2:
score: 0
Accepted
time: 135ms
memory: 28472kb
input:
100 994289 1 7 5 0 6 2 4 10 10 3 4 3 4 10 4 3 4 4 8 10 7 7 9 10 2 0 2 10 9 1 9 6 0 9 1 5 9 4 9 7 3 3 6 0 5 4 9 9 9 7 1 10 9 9 1 2 2 3 5 0 6 2 10 10 7 8 6 5 6 0 0 2 9 9 5 3 1 9 3 4 5 7 5 6 8 2 1 0 6 8 1 9 9 10 6 0 10 6 0 8 0 4 4 2 5 2 6 1 4 0 3 1 10 5 7 0 10 9 3 10 4 4 8 0 1 5 3 10 4 3 3 5 3 4 10 7 4...
output:
9941839 621830 47055 26 2848 1038 22 1670 2100632976 1598 17 1583876182 1920 1132 13 1710845770 1394369833 842 2423 11 1499 1770461608 18 2298828464 1510686047 825 1187 20 1853291990 1519857506 2018 468649819 16 772876976 12 11 15 21 8 1442946636 1141 1398 1959682622 1076570978 2755095527 1185971632...
result:
ok 100 numbers
Test #3:
score: 0
Accepted
time: 158ms
memory: 18892kb
input:
100 506329 621 533 920 508 898 576 304 537 836 558 993 46 119 12 507 84 922 882 523 625 229 483 98 52 612 739 894 446 137 897 255 343 431 710 800 511 888 944 516 971 603 145 375 443 294 788 68 37 569 307 218 107 777 231 548 325 924 503 618 108 738 813 989 576 6 961 568 842 193 412 718 541 786 746 56...
output:
505119187 215616108 1911749 12105955 27490340183643 17025740694399 18279490106845 6189115765782 467644 2195680587998 3462 70700746995 89490 8799 20 3618 1842 1982 33 1026 2495166430 1771 1968828958 981 20 972918546 937597910 18 18 11 1597 1674 1305 11 2016 10 1067 10 20 2232810137 2119 703 1720 1793...
result:
ok 100 numbers
Test #4:
score: 0
Accepted
time: 149ms
memory: 24656kb
input:
100 579358 6 10 3 10 0 8 5 6 9 10 2 9 10 9 4 9 1 2 5 2 8 7 2 7 2 5 5 4 1 9 0 1 9 5 1 0 10 9 7 3 2 7 8 6 9 1 4 2 5 6 4 2 8 2 9 0 2 8 3 7 10 0 2 1 4 0 3 9 2 1 6 2 1 10 10 5 3 8 7 5 0 5 3 6 2 6 0 3 9 1 9 5 5 4 0 10 1 10 2 0 9 4 4 7 5 6 9 6 7 2 10 4 4 0 1 10 3 3 6 6 7 6 7 8 8 10 5 8 7 0 1 10 9 10 6 4 7 ...
output:
5792563 43521828 30172 2596275 69600648006484 28944302 1954510 35477 1660344 4236623 2737 1314489 5081 145689 131457716739 3214 4771 4348 13 14 17 1143177956 1014371613 23 1404941621 2401 1160378322 1003 714 1308 1575 1980 1584 1533 1649704272 1730 1664819908 14 18 16 18 1375 1620 2174937671 1340326...
result:
ok 100 numbers
Test #5:
score: 0
Accepted
time: 151ms
memory: 28432kb
input:
100 879556 7 1 3 0 4 8 3 2 7 8 6 1 7 10 7 3 8 10 5 7 4 5 3 10 8 5 4 2 1 8 5 8 4 6 5 10 9 7 8 4 10 3 5 9 6 4 6 5 10 1 6 10 1 8 1 5 4 4 1 8 8 3 6 4 10 0 1 7 5 7 5 6 5 5 4 5 10 10 8 6 8 3 7 9 5 7 4 7 6 8 6 6 7 7 10 10 5 10 4 5 10 6 7 6 6 7 0 6 10 9 1 7 7 8 10 1 5 9 1 0 8 9 2 9 6 0 1 8 0 9 10 2 3 0 9 2 ...
output:
8794527 695476 17517824446575 20429382230551 8519621068970 2945813198379 57561 989 12502 303 504 25 3631360051 2118188464 1904 8 843 1742872711 19 1952 13 1882 857656076 1796188272 20 1626 2063 1158069485 2230 1997867598 20 1706799850 2256095763 1839524452 1196196665 1635312911 928 1950 1700 10 14 1...
result:
ok 100 numbers
Test #6:
score: 0
Accepted
time: 179ms
memory: 15320kb
input:
100 343898 522 428 432 632 781 174 275 244 837 767 207 463 829 446 79 772 406 50 675 924 901 738 919 922 52 569 931 485 789 425 283 250 429 733 8 584 711 579 864 331 586 54 147 547 190 426 195 821 417 539 628 254 912 381 702 259 313 352 541 936 465 607 171 126 580 656 477 96 683 619 250 685 301 981 ...
output:
342869036 77223215712927 17096607 73508894421413 125457966076807 2458093 47533447634232 64968419935736 9177 533 15966058010 716 24 2399083905 9200 5 1935 2015324208 10 1213274929 514 2117196057 7 1816 15 1438 24 1725638390 2089821071 1518705143 10 22 1136 1895824983 680 1413368800 435210134 1425 8 1...
result:
ok 100 numbers
Test #7:
score: 0
Accepted
time: 174ms
memory: 17852kb
input:
10 496790 8958078 276654289 140900625 930632767 575423054 371285906 189517172 667687980 917128959 617016421 433537199 984467537 78957976 299645227 812411985 434672063 869196615 676367981 54299805 385959649 299752118 952401009 769842649 625452964 655467837 522584259 201017076 579108741 984032550 1355...
output:
495375852683342 91497867698628 22674406551525 3683552 16828162 1393322 887435512038 64678 25164314549 76288
result:
ok 10 numbers
Test #8:
score: 0
Accepted
time: 152ms
memory: 27676kb
input:
10 686360 399 339 934 335 615 408 279 970 208 125 775 813 312 640 654 23 65 338 122 724 770 511 331 464 110 68 201 963 196 451 700 423 662 125 186 345 467 884 53 842 459 696 732 565 315 259 723 742 879 855 602 277 605 242 645 910 496 66 195 812 66 547 108 189 483 103 317 126 637 698 807 930 135 141 ...
output:
684992801 1904963 55884309 506938 15577533 17861 1214 3277769210 54 12
result:
ok 10 numbers
Test #9:
score: 0
Accepted
time: 176ms
memory: 16424kb
input:
10 28838 7 8 10 6 0 2 2 0 9 3 10 6 2 0 9 7 8 3 8 7 9 4 9 3 7 0 4 10 10 10 10 2 10 0 7 0 9 1 2 1 3 4 0 10 5 2 3 2 8 2 2 5 3 6 8 1 8 2 6 0 10 5 6 5 2 4 8 1 6 0 6 9 1 9 9 5 6 6 10 0 9 5 7 1 1 9 10 2 7 4 3 5 6 10 10 8 5 8 5 8 6 2 4 10 5 2 6 6 9 6 4 1 7 7 6 6 5 10 1 1 7 2 7 5 5 7 7 1 4 4 10 10 7 2 9 1 9 ...
output:
287676 191911333 474817182 247221809376299 53675871895235 21328694393 21073305860 29 1920422851 3764097950
result:
ok 10 numbers
Test #10:
score: 0
Accepted
time: 218ms
memory: 27808kb
input:
10 989853 333819042 442913096 961636514 826909247 939121958 164043745 939163818 93708408 844379314 805602467 942293407 903436360 441409621 945677607 420408739 565447266 455135173 918759203 701427472 902100175 57115739 463640972 171383001 496339956 131315824 737022441 248370749 73258978 646926546 319...
output:
987867968858964 40897 5028710899013 14255793542 664289 378 22721842753 1602648309 1648303511 60
result:
ok 10 numbers
Test #11:
score: 0
Accepted
time: 206ms
memory: 27340kb
input:
10 724888 806316452 232052093 738316941 978671463 695251912 362499421 161182270 164468691 436028842 893245183 653727460 720881181 902352079 77907698 628906272 146424528 902001812 385388870 753053557 555975713 759499248 165332103 863227880 385192247 820170136 877145786 514434574 502028115 115562868 8...
output:
723190180646362 244640887 20196295 549252546821 7442917160294 486193017258 10726800345 242815434560 27753 789
result:
ok 10 numbers
Test #12:
score: 0
Accepted
time: 154ms
memory: 26536kb
input:
10 466436 716 531 124 374 554 322 287 990 348 222 717 833 612 482 849 125 930 759 378 610 344 459 868 141 932 871 672 997 957 394 286 356 591 23 496 677 398 43 57 823 981 652 866 825 920 792 782 743 322 514 238 828 599 338 589 723 182 186 33 928 453 871 1000 657 221 203 0 887 535 19 114 216 245 878 ...
output:
465265500 5261127 6630033467982 289926193384 97741945585 15912504822 33660 20270919069 4497 110
result:
ok 10 numbers
Test #13:
score: 0
Accepted
time: 174ms
memory: 28636kb
input:
100 994289 109 703 3984 4003 5035 7372 8368 8985 9632 10431 11626 12256 12768 15260 15704 15775 15816 16926 17126 17374 17849 20483 21996 22239 23043 23232 23328 25630 25645 27105 27574 27824 28131 30046 30364 30528 30722 33608 34003 34472 35481 37599 38352 38973 39329 39677 39906 43579 47449 48490 ...
output:
806020169690585 694117452441 2781600005558 148743333152 842517087200 4321644703 2355455990 1898310428 2024348339 869783435 2203088508 1940113505 1198185344 1977712594 1794167592 1113443580 1601611452 1017901375 1886833802 1614359711 1881179050 1538838027 2280761436 1090265498 1923320194 2080363158 1...
result:
ok 100 numbers
Test #14:
score: 0
Accepted
time: 172ms
memory: 16628kb
input:
100 506329 1012 1042 1082 5973 6995 9541 11673 13219 20729 20956 20986 24891 26641 27848 29452 30359 31108 32441 32586 38115 40799 42745 43817 45129 45326 49211 51435 52790 54298 55449 59929 60282 61925 63731 68010 69166 71719 73103 75324 75943 80957 81353 88655 88739 89229 90183 92862 95572 95971 9...
output:
419679424205199 97940527507756 95327329631004 45302444376732 17147041929286 144704769414885 3006338153839 1649158480775 25606664358 6338018402 3264734592 1759734603 2051397932 1491557562 1652224260 2624745640 572062028 1754344646 1442879024 1101406992 1064935862 1138607763 1650666465 1077277230 1313...
result:
ok 100 numbers
Test #15:
score: 0
Accepted
time: 169ms
memory: 26004kb
input:
100 579358 1081 1751 2146 4556 5121 5805 5962 9307 11409 11711 12320 21107 21114 21707 24491 26736 30932 31508 33786 34117 36581 36966 36988 37206 38560 41485 42132 44599 44708 46887 47384 50879 53956 54439 54573 54721 55677 55950 60017 68027 69915 72464 73208 77548 79107 80893 83805 84547 85281 871...
output:
491864088985704 206170580949553 111222318669151 37171495353758 754324394143 45993783498 385131528009 162438302334 14820540948 23400291920 796132814 962357345 2183636767 2575182135 1535357270 521851903 2686940642 1104097171 831779113 1763580257 2209079835 1595480163 1835757392 1235852718 1698968414 1...
result:
ok 100 numbers
Test #16:
score: 0
Accepted
time: 171ms
memory: 27968kb
input:
100 879556 215 1509 2530 3179 3669 4356 4506 4991 6000 6158 7018 7799 7870 8412 8868 9105 11002 12635 15872 16428 16555 17330 18064 18332 19397 20155 20169 21813 22125 23134 23508 24673 25807 29113 29383 33530 34875 36303 37310 38024 38219 38656 39919 40599 41915 42095 42607 43579 45242 46012 46207 ...
output:
737659960145815 74528071514186 15448464655909 8885660350373 217485109353 6994175274 158131825971 170211992981 1612564060 2340321884 2222249270 804280597 1856739329 1924528074 1545904089 664042332 1017171691 1473799606 1868597667 2025311105 1657523545 1490822782 1822236449 1125819166 1687249997 14856...
result:
ok 100 numbers
Test #17:
score: 0
Accepted
time: 162ms
memory: 16200kb
input:
100 343898 3130 3868 6129 8628 20562 21601 25521 26049 39257 43978 45528 47589 48203 51113 54384 59537 60016 60751 61063 64036 72432 74574 79564 82578 83337 84393 88083 90334 91413 92195 97833 104775 111916 114613 114746 115307 117001 118670 123309 124196 124467 130761 140534 143231 143589 151731 15...
output:
291767350216528 35486190016871 65483785173553 67894479614221 97667230127910 176838276499269 11024076869064 7575160766438 21072980925268 42370606822641 1423031842822 166271725525 46143665571 2773091640 2108054540 5185015038 1566331108 1850771120 1448935366 1669124178 1211066272 1421720384 1738728088 ...
result:
ok 100 numbers
Test #18:
score: 0
Accepted
time: 170ms
memory: 18496kb
input:
10 496790 4973 6431 6944 8378 11680 12740 15361 18438 20984 21933 22540 23974 26434 27460 27603 27697 28490 28830 30494 30821 32578 37621 42443 45288 47325 48453 55427 58389 58491 59370 63391 64124 64438 65157 74677 75550 75700 77280 77759 78226 79143 89081 91078 91091 92757 94025 94572 95176 95508 ...
output:
414587193614540 340078983485161 41957595188390 3029106434165 18701107668813 8166358359515 24082064280 336999000224 215506558438 167348418143
result:
ok 10 numbers
Test #19:
score: 0
Accepted
time: 175ms
memory: 27412kb
input:
10 686360 1307 3748 6844 6999 7319 9510 9776 11069 15300 16417 17077 18232 20245 21169 22168 22192 25941 26190 27245 28241 28313 29594 30440 33430 34934 35370 39800 40704 40827 41301 42368 42437 43111 44819 44863 45853 46751 46973 48721 48956 50542 51377 53360 53479 53700 53859 55155 55882 55905 562...
output:
560667786996319 100386138576498 9134452533268 87787511919288 27713286795947 13998878616927 5806230959168 2315974589896 1715581610638 6145086222916
result:
ok 10 numbers
Test #20:
score: 0
Accepted
time: 161ms
memory: 17892kb
input:
10 28838 77078 77787 86737 153252 181708 197448 200261 272475 284723 350194 384364 388197 411650 426592 450525 491338 493023 493300 540912 553815 576704 588057 633001 689153 726941 806909 817561 828818 887686 926815 1006979 1010737 1091541 1128144 1158198 1191307 1195574 1257237 1275619 1451058 1481...
output:
24484365012917 341085653959825 339157100061842 97599365608724 38652094703111 9825073900148 130979102964 813392259554 496579848457 241319569240
result:
ok 10 numbers
Test #21:
score: 0
Accepted
time: 166ms
memory: 28732kb
input:
10 989853 1410 2594 4332 5389 6252 7798 9736 11388 12159 13717 14455 16408 16548 16713 17228 17271 19975 20117 24092 27818 28018 30407 30696 31288 31908 35072 35147 37155 37257 39809 41110 41615 41921 42006 42669 42834 44412 44629 45332 46095 47827 48363 49677 50342 51514 52270 52482 52699 53024 546...
output:
804001100252680 1768269880063 5750701995779 523735622121 113665613228 6647771156 63680276506 80893114015 21314166005 48595831468
result:
ok 10 numbers
Test #22:
score: 0
Accepted
time: 163ms
memory: 27412kb
input:
10 724888 11 1711 2817 3812 4856 4920 8089 12074 12724 13314 16612 17175 18435 18711 18889 20655 21237 22193 22227 23014 25093 26140 26747 27557 28089 30809 31464 32645 33736 34752 36583 44405 46548 47547 48491 49194 49320 51199 53113 54689 57721 59964 60371 61898 62010 62081 64699 64702 64957 66804...
output:
595762975828912 45135425697909 40426142508794 135225617181794 4061268995290 80613314201 353963369037 1891405928 1833884456 1440406579
result:
ok 10 numbers
Test #23:
score: 0
Accepted
time: 178ms
memory: 27572kb
input:
1 1000000 999999999 999999999 1000000000 999999999 1000000000 999999999 1000000000 1000000000 1000000000 999999999 999999999 999999999 999999999 999999999 999999999 1000000000 1000000000 999999999 1000000000 1000000000 999999999 1000000000 999999999 999999999 999999999 999999999 999999999 999999999 ...
output:
999999999500056
result:
ok 1 number(s): "999999999500056"
Test #24:
score: 0
Accepted
time: 182ms
memory: 27768kb
input:
1 1000000 999999909 999999969 999999990 999999996 999999987 999999948 999999933 999999947 999999976 999999968 999999957 999999938 999999987 999999994 999999988 999999912 999999949 999999918 999999917 999999907 999999941 999999994 999999958 999999951 999999916 999999939 999999975 999999961 999999997 ...
output:
999999950050591
result:
ok 1 number(s): "999999950050591"
Test #25:
score: 0
Accepted
time: 207ms
memory: 28088kb
input:
1 1000000 999994028 999990467 999997960 999994027 999999097 999997637 999993965 999992302 999995309 999991513 999992925 999992491 999993614 999997104 999996969 999998498 999992901 999993369 999992713 999996541 999990393 999991605 999996291 999997203 999991960 999992167 999999943 999997807 999992411 ...
output:
999995665953616
result:
ok 1 number(s): "999995665953616"
Test #26:
score: 0
Accepted
time: 217ms
memory: 28528kb
input:
1 1000000 999613965 999558506 999239219 999984415 999551694 999277568 999100687 999477889 999118151 999196501 999699532 999484216 999199330 999328077 999693164 999811872 999912705 999961392 999987747 999415268 999525371 999931570 999752970 999500732 999811339 999108492 999322081 999828265 999639472 ...
output:
999938909418747
result:
ok 1 number(s): "999938909418747"
Test #27:
score: 0
Accepted
time: 218ms
memory: 28668kb
input:
1 1000000 916124547 982152769 956607918 975811202 956580804 979234033 970043298 942048474 946499933 947536901 953520894 955455346 970596658 961798157 939068802 956472343 962834351 932654402 925181107 932392063 999789753 915341031 941950179 995099158 992267918 972551357 933819264 982794855 916558930 ...
output:
999369789602821
result:
ok 1 number(s): "999369789602821"
Test #28:
score: 0
Accepted
time: 215ms
memory: 28312kb
input:
1 1000000 634477439 282519115 334616450 269434111 888016674 753775009 219222080 276577175 105938749 945655376 885815877 311120234 269798774 57928095 636469465 78767370 437425438 775069992 592212957 638131054 211958860 470430565 528338569 306914450 989525157 591625421 758553299 424558696 923316689 50...
output:
997991062944867
result:
ok 1 number(s): "997991062944867"
Extra Test:
score: 0
Extra Test Passed