CT65309

Asha Counts the registers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Every season at the gull cliffs of Screech Point, someone must fulfill a tricky customer order. This year the task falls to Asha, armed only with the registers register. 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: 1276 409536580 177089308 391626813 546613532 721636573 177196475 277627883 623934246 542628396 635958876 787108363 157081566 607275090 734540237 329300759 234109683 81517593 706877540 377734461 274315521 676594243 777827026 214687691 759394664 576581299 803223590 485337771 719606687 345946741 965206697 331419408 605647844 350179371 195512450 675789806 712308809 890657318 587312540 708176979 478319987 144220072 345898568 183656788 102825949 56997732 974474068 809108898 689831929 76951138 247054755 77040039 650687408 719409228 734310983 78186343 756927362 891914073 47686438 46795530 755177387 569692888 760276687 569165759 71482860 735435502 165848126 571042594 807795297 494861069 834582669 986793567 693911185 941114297 109067266 818772316 418903435 550335985 19135985 15243165 829798480 66746…
Output: 9712431400

Example 2:

Input: 1494 496317215 391055697 926984788 7862586 545937720 417265284 356471823 42523975 529785434 678082030 613468038 495169666 347422823 732953575 914229715 435896326 104889039 270530408 884998551 859446745 416770303 463004384 1171283 635083440 272135492 522664149 206891632 559619833 529089287 364405929 838759623 676419420 641855799 140295785 934264739 103920107 401024636 910373922 467817119 991672847 930575042 312574372 809836152 834145940 979807900 57687142 852603039 271248264 794886033 66591436 84532616 941497501 963938900 953823477 933324196 952237048 873241733 257260640 268767133 866011625 743898396 780679750 317360809 141821706 188553570 578817934 811348 13489597 430938040 876811765 543251210 469710046 825203138 492019849 137452267 178644098 464532664 524079536 827594465 700253585 3652751…
Output: 7110150320

Example 3:

Input: 3432 188816252 913943377 222152735 468503483 219082676 715899360 458059956 135449348 274197846 447625661 208705864 194550608 304818518 842964950 867691449 586659000 55673819 599385328 799763499 761839999 337898930 55818364 718581950 777635627 53088512 918107904 657934330 568845389 594047913 811621633 705357740 731989993 673310350 652237592 922372646 799404964 203046906 88474673 796201257 535461721 979450595 953940568 807459980 259674160 924739361 103214757 455693268 700587118 317690748 666920667 424802619 343629791 277288600 143961583 324329320 877044041 939667948 951159459 364006351 312979569 654487909 344296957 929687812 756538637 928560943 325614281 146002999 331678710 590658085 247641767 61334229 941531115 406421350 363096913 809181888 435146272 461915268 92174040 208766826 883454531 2…
Output: 11275654500

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Asha Counts the registers - MEDIUM Coding Problem | CodeTikki