CT64861

The Topaz registers of Dorian

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the boar woods of Tuskmore opens only for a perfect tally of registers. Dorian means to find out. 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: 544 534640267 794820569 336176933 320041799 816899489 605457830 710752315 714264418 509440679 387479219 335998555 8387995 923636308 430207618 744212441 432672991 311983648 478914852 675578693 334674807 332366699 446063150 264348643 542043956 795333958 688806914 307803819 615663267 680251702 550425005 291854161 23380707 545216144 959140434 101484866 919410426 29706823 57850397 33671254 586976530 709661365 658571662 596059223 80007865 736258451 763605309 199743014 608608507 718357316 274499572 851007915 587674664 280623865 109339201 90672394 523142790 373417233 526419784 829378703 263023883 885279726 889189261 143760758 75319621 275323840 762380998 714090499 84525183 762906935 889300973 610747160 142807247 993553152 347210799 301543971 826231763 869084701 679483612 586198956 938849624 865507…
Output: 5022624217

Example 2:

Input: 2390 195763777 927645526 857349759 891577798 787599197 317819093 592543464 460969517 392870037 98193967 14491232 887309744 290435818 151690335 786610902 968408780 734419054 65445695 39333166 778002705 869205586 628636686 444680882 323880074 681523819 879683583 952644117 334077043 998564088 929536600 743674605 667226611 954620380 854038622 446151131 7314272 796641411 500157074 816370273 951536782 59855033 500379444 457870224 886382969 397916441 906411017 345987766 154258973 382763381 404321199 319361706 675888211 103364793 715197180 954681075 25317523 728667248 391485546 938941029 436089880 617182410 279586309 435963940 895571102 454268753 608558915 443642258 808330321 48176835 18733856 308797069 873691775 225564587 765024383 443747979 819480136 988263033 143682926 552188007 616938276 21380…
Output: 7653505080

Example 3:

Input: 1444 412389840 841084297 687756079 946831560 114818070 646517674 587224892 400352278 729840338 688497158 383891630 429473874 21186054 794110970 86803266 506458582 141262850 109464644 488526357 319560819 858911404 778129172 607573139 776613261 382657087 954343681 998669791 559371217 503991588 930028568 942800430 737987233 198189538 257090710 242011960 107975903 413871846 564247962 639454749 149207859 907897919 68899408 638343605 830751957 908163654 70605947 819984133 844331350 479465043 245646948 250553338 672651296 84494963 14026262 512275271 145692828 526905534 604586861 301581422 210285300 752925668 294398787 547080787 471758456 394867108 14336121 444701200 522377091 952257237 817901844 100913587 771016520 536259681 767933458 776676587 863423543 19538350 73108743 454784146 431067999 8303…
Output: 5419360954

Constraints:

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

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