#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
#define int ll
const int N=1e6+99,S=2,inf=1e16;
int n,t,ans,a[N],res[N],ps[N][S],L[N],R[N];
set<pair<int,pair<int,int> > > s;
void Add(int l,int r){
if(r>n || l<1) return ;
int res=(ps[r][1]-ps[l-1][0])-(ps[r][0]-ps[l-1][1]);
s.insert({res,{l,r}});
}
void del(int l,int r){
if(r>n || l<1) return ;
int res=(ps[r][1]-ps[l-1][0])-(ps[r][0]-ps[l-1][1]);
s.erase({res,{l,r}});
}
main(){
cin>>n;
f(i,2,n+2){
cin>>a[i];
}
n+=2;
a[1]=-inf;
a[n]=-inf;
f(i,0,(n+1)/2-1){
//cin>>res[i];
}
f(i,1,n+1){
L[i]=R[i]=i;
s.insert({a[i],{L[i],R[i]}});
ps[i][0]=ps[i-1][1];
ps[i][1]=ps[i-1][0]+a[i];
}
f(t,0,(n+1)/2-1){
pair<int,pair<int,int> > p=*s.rbegin();
int copy,l=p.S.F-1,r=p.S.S+1;
R[l+1]=0,L[r-1]=0;
//cout<<l<<" -> "<<r<<endl;
s.erase(p);
ans+=p.F;
copy=l;
del(L[l],l);
l=L[l];
L[copy]=0,R[copy]=0;
R[l]=r;
copy=r;
del(r,R[r]);
r=R[r];
L[copy]=0,R[copy]=0;
L[r]=l;
Add(l,r);
R[l]=r;
L[r]=l;
cout<<ans<<" ";
}
}
/*
1000
545 824 764 528 811 257 205 85 446 924 646 791 35 40 942 422 457 364 984 103 940 622 306 45 583 637 924 193 727 849 121 189 938 625 218 654 185 125 393 625 906 886 851 263 633 131 786 27 471 109 506 340 955 172 482 990 577 667 213 406 200 634 226 517 577 195 552 428 572 519 694 994 157 562 882 602 991 396 649 944 679 249 271 621 437 291 886 585 382 911 916 585 542 830 49 617 900 940 734 995 822 158 140 897 583 528 811 87 462 900 458 349 297 882 343 483 737 348 768 46 615 481 513 250 760 605 654 864 509 950 388 515 790 362 963 525 961 271 62 639 709 612 110 281 539 390 140 334 751 613 342 76 284 777 604 490 174 887 771 891 468 832 489 947 413 515 898 631 297 33 643 585 708 26 237 500 551 535 964 525 688 120 865 403 859 111 677 337 416 276 702 817 695 569 135 963 938 369 651 222 762 965 754 662 748 240 975 791 636 596 937 281 299 35 561 317 206 11 571 462 895 132 417 627 880 203 772 108 621 972 964 563 217 203 874 942 892 716 196 730 27 533 601 698 416 592 389 359 652 453 479 946 634 719 690 721 334 149 505 334 334 276 550 710 688 868 908 976 52 448 275 148 883 290 84 583 648 390 279 100 453 165 481 972 898 597 729 362 834 575 253 0 958 994 89 742 358 990 880 421 149 563 789 902 828 258 404 80 914 325 733 594 258 555 777 669 29 390 16 534 547 633 362 571 452 972 68 764 411 122 166 340 181 253 122 639 111 48 160 278 214 892 152 993 178 15 919 805 454 627 301 782 105 619 758 454 552 355 873 135 120 496 725 438 231 542 858 264 442 713 375 137 556 189 744 402 22 850 578 555 834 594 770 370 532 349 954 698 611 424 230 8 756 25 943 594 616 821 317 473 231 526 890 24 797 375 916 485 452 882 316 199 219 485 645 889 85 87 654 991 220 753 532 326 751 371 786 793 274 12 90 217 278 511 433 948 336 210 350 697 670 849 507 195 896 18 351 420 643 546 378 660 51 752 211 986 698 416 111 962 148 939 739 472 846 68 316 324 350 286 460 215 196 5 952 172 1 51 351 834 318 652 534 210 89 963 666 980 652 486 358 902 31 952 94 239 823 885 42 209 862 27 631 774 316 752 802 637 446 734 79 28 847 550 113 16 861 460 803 555 829 591 622 53 489 4 188 542 97 331 164 835 672 458 519 135 712 240 795 964 224 589 933 922 197 833 533 862 439 914 260 983 838 257 353 30 404 183 557 196 949 988 891 537 892 665 516 313 224 71 321 241 103 431 354 691 497 307 24 942 976 364 414 258 54 926 581 90 968 337 776 274 354 890 13 827 947 337 749 117 154 828 893 125 161 212 750 303 33 766 707 318 167 916 145 233 709 21 763 128 148 683 86 104 680 283 210 858 36 763 851 843 968 7 607 751 560 412 265 984 559 448 821 230 252 505 69 719 500 182 707 913 760 803 536 340 760 401 284 958 207 525 655 882 825 856 679 361 467 415 779 979 218 507 728 559 551 899 305 81 282 729 37 692 628 811 372 593 353 923 153 790 285 345 31 810 814 70 981 832 435 901 211 867 619 382 138 825 161 466 943 714 607 734 800 514 193 953 114 797 147 208 91 731 173 469 355 301 414 564 968 223 719 614 146 405 529 192 884 955 489 406 341 496 187 949 166 907 134 543 252 145 990 370 720 29 783 51 669 513 105 695 217 227 959 434 744 684 412 739 686 517 256 984 828 867 199 342 885 734 211 956 776 852 195 968 88 571 108 2 355 862 455 808 192 415 803 537 597 814 893 342 616 257 261 598 468 525 442 633 830 571 264 703 184 391 233 10 61 653 987 905 694 93 569 927 941 297 980 699 569 931 523 233 97 253 544 945 364 955 717 918 760 563 910 594 938 793 737 256 390 212 732 338 774 669 638 60 168 257 761 297 491 893 318 860 443 297 993 553 54 904 446 350 789 566 308 36 7 347 802 610 946 128 272 548 419 615 86 432 392 88 730 537 469 417 686 423 316 822 577 551 344 369 519 455 915 76 467 269 94 828 452 728 186 848 77 543 653 211 730 945 559 454 784 693 805 409 732 34 37 363 503 665 547 913 984 50 956 227 402 133 177 109 103 251 990 533 398 235 771 760 385 488 195 962 826 867 612 869 487 558 742 401 827 689 943 118 47 96 918 30 209 532 430 14 404 729 54 214 328 832 343 823 187 166 949 325 376 301 433 285 143 769 454 56 150 14 316 56
995 1989 2983 3976 4969 5960 6951 7941 8931 9921 10911 11899 12886 13872 14856 15840 16824 17808 18791 19772 20752 21732 22711 23687 24663 25638 26610 27582 28554 29522 30490 31458 32426 33391 34355 35319 36282 37245 38208 39170 40132 41093 42052 43010 43966 44922 45877 46832 47787 48741 49694 50646 51598 52548 53497 54446 55394 56341 57288 58234 59180 60125 61070 62014 62957 63900 64843 65785 66727 67668 68608 69548 70487 71425 72363 73300 74233 75164 76090 77014 77938 78861 79780 80698 81616 82532 83448 84364 85279 86193 87107 88020 88930 89837 90743 91647 92549 93451 94352 95252 96151 97049 97946 98842 99737 100630 101523 102416 103308 104200 105091 105981 106871 107760 108647 109533 110418 111303 112186 113068 113950 114832 115714 116594 117467 118336 119204 120071 120938 121805 122670 123534 124396 125258 126120 126981 127841 128700 129558 130416 131272 132124 132976 133827 134678 135528 136377 137226 138074 138921 139767 140602 141436 142270 143104 143937 144769 145601 146431 147261 148090 148918 149745 150570 151394 152218 153041 153863 154684 155505 156322 157136 157947 158758 159569 160377 161182 161985 162788 163591 164393 165195 165995 166792 167589 168382 169173 169963 170753 171542 172328 173112 173895 174677 175454 176231 177007 177781 178555 179327 180098 180868 181637 182405 183171 183935 184698 185459 186219 186979 187737 188493 189246 189998 190749 191500 192251 193001 193750 194498 195242 195986 196728 197470 198209 198946 199683 200417 201150 201882 202614 203345 204075 204805 205534 206263 206992 207720 208448 209173 209894 210614 211333 212052 212771 213486 214199 214911 215621 216330 217039 217747 218450 219148 219845 220540 221234 221926 222617 223305 223991 224674 225354 226031 226700 227367 228032 228692 229346 229999 230651 231303 231954 232602 233245 233888 234527 235165 235801 236435 237068 237701 238328 238950 239571 240188 240804 241419 242034 242647 243258 243865 244463 245060 245653 246245 246832 247415 247995 248575 249153 249730 250302 250873 251444 252015 252584 253145 253702 254258 254810 255362 255913 256464 257015 257563 258106 258648 259190 259729 260263 260796 261328 261860 262389 262914 263439 263958 264477 264994 265510 266023 266534 267040 267545 268050 268546 269036 269525 270013 270499 270984 271469 271942 272413 272882 273351 273818 274285 274745 275202 275655 276103 276550 276983 277415 277846 278267 278685 279102 279518 279934 280350 280764 281178 281585 281991 282395 282799 283201 283599 283992 284383 284773 285163 285548 285932 286314 286690 287064 287417 287768 288118 288467 288812 289156 289498 289838 290176 290510 290841 291166 291487 291805 292121 292437 292746 293054 293361 293667 293966 294263 294550 294828 295095 295348 295601 295854 296093 296330 296563 296794 297024 297248 297465 297682 297896 298106 298316 298524 298730 298935 299134 299330 299521 299698 299872 300040 300201 300361 300519 300673 300823 300969 301109 301231 301351 301464 301574 301681 301785 301888 301975 302062 302143 302221 302282 302333 302381 302428 302466 302503 302510 302512 302511 302469 302391 302311 302228 302129 302005 301875 301739 301596 301453 301281 301085 300875 300625 300374 300111 299818 299509 299151 298753 298327 297838 297315 296771 296226 295638 295015 294367 293686 292975 292262 291500 290651 289735 288787 287209 285616 284021 282226 280313 278276 276222 273672 269356 264699
5
3 5 1 7 6
7 12 10
20
1 5 7 4 1 6 5 4 7 6 7 8 9 7 4 2 3 2 1 4
9 16 23 30 36 40 44 47 49 48
50
5101 15771 20482 15590 21148 25161 20231 19178 4252 21604 18338 31380 8817 29875 15505 5241 31720 16155 29743 22362 27469 26889 11591 10666 5343 16149 5670 1099 17025 1503 14836 31385 23474 25149 22596 937 6591 3225 23273 26834 19511 21396 24075 32109 16800 12783 32379 986 10344 31660
32379 64488 96208 127868 159253 190633 220508 250251 277720 304554 329715 354864 376468 397864 418346 437524 454549 470698 482289 493168 499759 504131 507451 502315 457630
32379 64488 96208 127868 159253 190633 220508 250251 277720 304554 329715 354864 376468 397864 418346 437524 454549 470698 482289 493168 499759 504131 507451 505477 549710
*/
Compilation message
candies.cpp:39:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
39 | main(){
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
464 KB |
Output is correct |
| 2 |
Correct |
2 ms |
436 KB |
Output is correct |
| 3 |
Correct |
2 ms |
440 KB |
Output is correct |
| 4 |
Correct |
2 ms |
588 KB |
Output is correct |
| 5 |
Correct |
2 ms |
432 KB |
Output is correct |
| 6 |
Correct |
2 ms |
420 KB |
Output is correct |
| 7 |
Correct |
2 ms |
460 KB |
Output is correct |
| 8 |
Correct |
3 ms |
460 KB |
Output is correct |
| 9 |
Correct |
2 ms |
460 KB |
Output is correct |
| 10 |
Correct |
2 ms |
460 KB |
Output is correct |
| 11 |
Correct |
2 ms |
464 KB |
Output is correct |
| 12 |
Correct |
3 ms |
460 KB |
Output is correct |
| 13 |
Correct |
2 ms |
460 KB |
Output is correct |
| 14 |
Correct |
2 ms |
460 KB |
Output is correct |
| 15 |
Correct |
2 ms |
428 KB |
Output is correct |
| 16 |
Correct |
2 ms |
468 KB |
Output is correct |
| 17 |
Correct |
2 ms |
460 KB |
Output is correct |
| 18 |
Correct |
2 ms |
460 KB |
Output is correct |
| 19 |
Correct |
3 ms |
460 KB |
Output is correct |
| 20 |
Correct |
2 ms |
460 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
464 KB |
Output is correct |
| 2 |
Correct |
2 ms |
436 KB |
Output is correct |
| 3 |
Correct |
2 ms |
440 KB |
Output is correct |
| 4 |
Correct |
2 ms |
588 KB |
Output is correct |
| 5 |
Correct |
2 ms |
432 KB |
Output is correct |
| 6 |
Correct |
2 ms |
420 KB |
Output is correct |
| 7 |
Correct |
2 ms |
460 KB |
Output is correct |
| 8 |
Correct |
3 ms |
460 KB |
Output is correct |
| 9 |
Correct |
2 ms |
460 KB |
Output is correct |
| 10 |
Correct |
2 ms |
460 KB |
Output is correct |
| 11 |
Correct |
2 ms |
464 KB |
Output is correct |
| 12 |
Correct |
3 ms |
460 KB |
Output is correct |
| 13 |
Correct |
2 ms |
460 KB |
Output is correct |
| 14 |
Correct |
2 ms |
460 KB |
Output is correct |
| 15 |
Correct |
2 ms |
428 KB |
Output is correct |
| 16 |
Correct |
2 ms |
468 KB |
Output is correct |
| 17 |
Correct |
2 ms |
460 KB |
Output is correct |
| 18 |
Correct |
2 ms |
460 KB |
Output is correct |
| 19 |
Correct |
3 ms |
460 KB |
Output is correct |
| 20 |
Correct |
2 ms |
460 KB |
Output is correct |
| 21 |
Correct |
340 ms |
23664 KB |
Output is correct |
| 22 |
Correct |
350 ms |
23668 KB |
Output is correct |
| 23 |
Correct |
338 ms |
23568 KB |
Output is correct |
| 24 |
Correct |
177 ms |
23440 KB |
Output is correct |
| 25 |
Correct |
176 ms |
23444 KB |
Output is correct |
| 26 |
Correct |
179 ms |
23456 KB |
Output is correct |
| 27 |
Correct |
194 ms |
23556 KB |
Output is correct |
| 28 |
Correct |
215 ms |
23572 KB |
Output is correct |
| 29 |
Correct |
192 ms |
23508 KB |
Output is correct |
| 30 |
Correct |
225 ms |
23740 KB |
Output is correct |
| 31 |
Correct |
200 ms |
23552 KB |
Output is correct |
| 32 |
Correct |
202 ms |
23552 KB |
Output is correct |
| 33 |
Correct |
246 ms |
23468 KB |
Output is correct |
| 34 |
Correct |
258 ms |
23380 KB |
Output is correct |
| 35 |
Correct |
265 ms |
23552 KB |
Output is correct |
| 36 |
Correct |
320 ms |
23548 KB |
Output is correct |
| 37 |
Correct |
332 ms |
23448 KB |
Output is correct |
| 38 |
Correct |
404 ms |
23436 KB |
Output is correct |
| 39 |
Correct |
171 ms |
23444 KB |
Output is correct |
| 40 |
Correct |
186 ms |
23400 KB |
Output is correct |
| 41 |
Correct |
176 ms |
23364 KB |
Output is correct |
| 42 |
Correct |
199 ms |
23420 KB |
Output is correct |
| 43 |
Correct |
201 ms |
23548 KB |
Output is correct |
| 44 |
Correct |
211 ms |
23416 KB |
Output is correct |
| 45 |
Correct |
201 ms |
23448 KB |
Output is correct |
| 46 |
Correct |
205 ms |
23500 KB |
Output is correct |
| 47 |
Correct |
260 ms |
23388 KB |
Output is correct |
| 48 |
Correct |
282 ms |
23364 KB |
Output is correct |
| 49 |
Correct |
251 ms |
23440 KB |
Output is correct |
| 50 |
Correct |
267 ms |
23468 KB |
Output is correct |
