CT61529

Seth Counts the marks

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Seth the measurer watches over the eel marshes of Slitherwick's stores of marks. A careful computation stands between order and chaos. 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: 1845 358305617 245136050 609115820 123187849 601487853 623911504 114430439 577123757 47673829 740610214 743047620 218863868 816037146 287268212 726319063 27124957 589220283 977048222 341438312 869730150 352328126 83720330 967232283 30930689 184058633 961641059 218748637 586304044 860509 924374329 30283740 961249270 672866420 138023154 783283382 472244587 229886259 646169597 864239840 714891796 154092820 49714712 472435894 720436837 597526027 749991728 107377667 179456938 454277731 753783930 911721328 650954223 539106143 237294600 556116614 135984865 249717522 231013183 421895150 871095920 787332419 161865023 495559552 333490144 201085410 418565840 613286722 853535538 459155690 336263415 501893253 115707698 360841394 278605778 480065595 5529550 616994107 747846068 147226603 835347796 655258…
Output: 8477737140

Example 2:

Input: 1389 42531973 564411497 306681126 206327577 748687626 402477430 745721898 417696823 301729648 581895464 271639250 38314587 302996807 944011550 2997690 771446236 451015762 464811891 377874742 101784348 218684088 916334580 168202372 768653534 854580818 967588478 141757931 141787158 766592502 721074821 562323085 894817229 887353779 135026986 317052470 376698430 902415039 138947000 738980525 337040189 340354074 539159356 258849473 38048046 946935759 47344156 148251228 337345404 579143429 586625356 276245851 179687626 291555799 525756743 396029237 113706124 886190901 563695770 377921088 871740443 38514069 410575367 269938134 175579739 468331344 67642424 847461152 510189853 304859609 782320090 456764465 806413129 798641910 690018052 892722026 973900432 676140208 308546312 561757678 44410331 1926…
Output: 5919121368

Example 3:

Input: 2123 528438361 235766583 775731048 330910105 631699097 20518932 959125820 64200690 998165653 573206701 563210335 673055501 991204110 320139383 297623141 487642884 539443230 615154803 689847619 986914848 583393909 245013035 708628523 288729866 558947168 215261680 26407505 119553886 224759458 895520722 330094613 429860466 843663509 137313480 451140044 680924789 836385759 180599673 895200049 242529157 964468576 674414716 891355868 551368894 918387658 671049638 242897179 893239717 613280571 282944817 972360166 885553125 838450133 736820640 933691667 245197565 198641757 570449083 448236419 66462751 463387295 256643500 230120487 650992314 365174006 888143506 187786222 643131220 219296361 164110000 845149187 932307207 770275551 152387714 538333655 816720914 138189945 798600847 93402032 583330182 …
Output: 6689064900

Constraints:

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

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