CT60128

Last ledgers of Rowena

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Every season at the mangrove channels of Rootwater, someone must prove the quality of the harvest. This year the task falls to Rowena, armed only with the ledgers 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: 579 618340862 224264862 934271305 861344354 254692885 936256167 403459728 956321008 609355695 320375784 418810373 598404305 160854417 104205731 847318941 191417535 37837790 724651043 365899415 919015588 977730835 867450284 754344880 968640987 289406542 393648865 139972679 644333352 383148501 661095236 436007830 102912682 947382106 879102125 866821846 421363629 685905961 303384636 570677118 368117840 125538796 796530205 70606848 682782150 419452332 541683789 398957180 548920408 898741537 134719567 448144449 975170371 455503411 68237095 384800934 577537676 398733635 529024160 753785242 719753589 918040534 364475735 762859372 719910521 507551784 188544722 138814857 708836320 762958371 977549620 235483376 285200635 555402240 389011928 543705845 150777800 535405250 465846491 812926884 778607884…
Output: 7920091485

Example 2:

Input: 3253 691624823 559946171 581743895 700471459 751356794 692245086 649520719 923814264 413897475 663089548 188154377 297964774 584114914 179723841 986710384 39597739 572362111 530962 705646483 60531754 845692255 733416701 502323842 792845070 762326925 377891323 537739723 945411254 769333581 35466876 743252933 840365875 392349118 722146668 578019201 539932277 193041447 298502802 50347329 508107018 505919846 690100748 106945889 44940496 631573706 876609641 545850435 764894283 73310298 279898742 280010118 638458631 764825200 677319886 629908517 813879591 975437033 501751578 598606019 152480528 850023612 65900754 168361522 54699109 269028206 967937767 780795397 384093711 351366288 904019801 672396286 505452868 465195012 568280817 428846433 98354728 608390112 230589822 325203499 259641906 9844151…
Output: 7209387999

Example 3:

Input: 2547 482470972 305862646 459397863 747403902 397371143 824265694 74870562 627908690 346249172 639108304 153239251 306775925 391868624 471641022 874852187 234292538 961683481 888784459 597747121 822230372 699621937 339558267 198783398 196525232 493691946 939953152 885570652 905646326 793370539 422204686 692464544 24655777 275843371 984202821 869352095 935176703 544715367 208941245 223823294 768301248 685907005 995337441 761696843 820653656 781198747 510300771 556781262 601502111 595921462 175137737 165345599 289890131 684953749 361759918 122523157 936850834 715059297 315418841 140929525 87495989 667143927 329885986 560359410 473419425 344999625 246046280 874716838 642633431 390355101 994550321 346129172 898960198 527438915 273469126 370047201 115159530 966855397 130112481 784920746 45478251…
Output: 8924070940

Constraints:

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

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