CT58016

Urmila's registers Reckoning

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Deep in the old quarter of Brasshaven, Urmila studies rows of registers entries. One clean number will settle the guild's oldest argument. 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: 804 185812776 640783678 225440945 118340636 667939869 722391620 542276255 528133241 73801972 655870678 600636696 964231017 400285250 183699790 492418219 889540552 964904547 351207929 148197374 900041722 633411239 2531542 405448655 807867763 70816591 114854648 460541320 4190257 963504442 406580642 119501923 451921169 276668858 2470812 215298706 60940566 803585426 483783605 608526019 828676510 590986753 596312872 864102302 379170522 509016336 768024559 164699073 550701099 253519431 376659265 835976362 840921446 92997536 814949979 743756982 33817767 419843461 217529050 429938165 461061155 622810969 656650133 154817722 897037644 126714509 873714933 241918702 68181539 393602784 940331194 986591739 592951351 60903974 795760915 29812627 63909106 971165366 483254594 82774006 8014960 726270450 1902…
Output: 8689229073

Example 2:

Input: 330 579438579 641270709 634017911 36769949 46660500 507305172 756417127 657128602 921210486 107545315 163590149 613805014 215253414 167358762 878251911 21778496 330997085 189198838 738967155 116159630 59965075 501074017 379370243 678209401 853011786 845563989 389278022 526462290 344497446 444697433 950744602 978971276 739117330 365045660 149922821 560152136 266042267 414814069 663328824 209573374 738065486 598913009 205348788 924408973 872032449 409026601 481358320 632151748 246945085 104777431 257583641 639387390 28055848 388171246 970572978 319626318 35984350 801926282 700958347 340376871 18395545 578487629 454132691 683554341 716917066 407408498 234120862 941753353 577426159 823777107 59389038 470632048 688579251 521169519 677464482 913529988 342485157 994186439 686179751 399485121 1219…
Output: 7109118096

Example 3:

Input: 649 707199327 220661026 631415435 395988091 305754559 632934012 946757962 2956834 390014193 900390271 785698697 306053244 428925724 182799284 430017313 470131098 990627788 832469084 863386737 484605386 884062116 81794666 600679374 843193806 931739602 825014039 473409960 837026646 653047540 7737 722418051 590487069 761956635 574903158 852725055 112899327 523064101 499175139 336845018 124063858 850183507 105983807 902866230 675453801 461841871 296947541 214539607 697827551 71502349 295019949 229171202 410015563 887736970 377662061 557807616 43612536 902053004 549964441 317453128 786876427 543153883 941854664 378367520 577144309 632240280 739010320 741014302 105881948 796769720 698242825 941539888 266968348 910631333 753364851 422853693 430695821 822043269 28292192 219341485 381846848 5071480…
Output: 8231932050

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Urmila's registers Reckoning - MEDIUM Coding Problem | CodeTikki