CT60416

The beacons at Crosswater

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The harbor bell rings at the ferry landing of Crosswater; Mina weighs the day's beacons manifests and starts the calculations. Task: Bars of heights h[i] stand side by side with width 1. Print the largest rectangle area that fits inside the histogram. Input format: First line: n. Second line: n heights. Output format: Print the maximum area (fits 64-bit). Constraints: 1 <= n <= 4000; 0 <= h[i] <= 10^9.

Example 1:

Input: 1353 348450351 76351064 777997600 29245866 90444784 583011433 224868998 313844434 877111274 937199373 704984648 217031133 489166620 534050278 710734712 675105253 811547829 943672143 389764416 960383916 964446571 812437544 218777620 123627715 133033042 950908500 765373792 826198896 275739612 396009603 318569456 727304993 731788312 442211312 706268888 227339964 657530274 787839818 382730950 358045445 883215198 493718911 682489767 553035678 922793338 391878893 518152287 644953867 6270837 159189393 958980871 957501529 920925819 312972992 974397607 774330511 109171530 52041580 845988713 512719206 310678365 338939386 998553173 503968853 786174937 179500414 291129639 838477137 281090417 787185776 742202249 971172126 642698821 923745483 46205314 862688156 133645844 206926527 973731429 65351695 369…
Output: 8045391200

Example 2:

Input: 466 67828781 613945680 453356271 988296723 418350175 720834869 219713114 651233583 227650292 230696364 119019709 160772850 856999954 328689224 424324578 108526292 943783656 996627185 186772993 755841080 768822569 199679458 494408145 524789152 688480883 393009262 644214532 767577355 499579163 38203596 75678129 208746903 486531843 704505815 838668707 742066793 584217634 577226618 461284201 512673478 865849710 793139855 832133152 37598694 858683793 829848828 425931525 664859296 218254905 942956289 591971516 377115884 80082082 243306687 448803264 926653461 645441602 148164922 343889581 919917918 64643780 989817096 15658887 317644814 597903816 882534691 20987421 265711169 979087297 453140904 511724331 916375854 198862871 826865205 804837656 928702216 991105080 495484924 959458843 154738759 8507…
Output: 5775201054

Example 3:

Input: 72 751741856 482814884 690706282 989904651 148543402 139755185 154497034 336863995 335515082 98948382 803045110 261471926 506385200 368962043 534890026 118688670 919467583 168465262 431858335 919943798 827699963 368869076 356870502 354612290 816816798 356161806 307948510 357015724 194387848 108460936 764490201 657178047 407827620 347216975 736864345 490622233 743962266 794818354 649144732 683624334 606717785 933984737 134078256 403590470 181400388 137546324 347795451 104015888 207588944 670123834 991317151 803973520 779350363 684301269 477081976 729568017 494360600 217096173 782464539 59022344 922372692 478172457 35165372 712943134 935858983 92384716 475363246 935157179 863003118 63640090 683894132 710947690
Output: 5837954538

Constraints:

1 <= n <= 4000; 0 <= h[i] <= 10^9.

Loading...
Test Cases:No test cases
No test cases available.