CT61764

Grey Counts the ledgers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Caravans arrive at the crane marshes of Stillwater with crates of ledgers, and Grey the registry keeper must account for every last one. 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: 1474 292542586 756768861 346131698 147434260 498264206 666132100 461656901 992056534 34264275 126243462 111333349 62059766 496459386 443441564 850815183 871473539 253010152 512897892 309705589 693219129 749709834 927934591 382673361 22775515 342257229 187619034 377219210 768430812 726179877 534524233 621600663 753992722 54232486 148245324 218258732 948200093 882613029 140940913 164355806 301206697 82961102 506451298 817751753 637625779 696418072 851731804 856711749 529463796 382862814 164569899 803169139 475439487 851201450 309733109 630723638 613362332 601232279 466232377 482531692 19071656 947450237 330201344 749017857 934703945 895950207 543183665 752937888 611191604 308132971 214673998 88765970 766907386 223662833 495962052 188806698 642097431 195359981 519855336 445994963 89847274 175…
Output: 10886401812

Example 2:

Input: 300 457778296 534999439 275887764 417513835 141184696 816011727 109398500 366402674 767426300 711526086 93482744 605681836 60914049 338448106 3701295 86559664 915558585 637785125 551538697 793266503 843747666 827193263 633048549 182345007 649047894 402486939 869726879 348999194 160423947 108407779 902747004 115656643 420910716 423947332 893886793 529075165 266800737 377713406 971552342 537308090 373793311 358624853 631495193 572065062 288862122 796284606 283747141 48054100 132609578 509795836 84001824 547205848 203445806 823053751 390689431 657792667 831165225 903791391 739803939 805945348 580678860 307803346 523705391 965626277 406311981 73935148 981253644 85992201 894837626 134533724 947116702 199494189 56854683 898694154 805327046 803154049 667937923 963683323 995849002 885528333 371771…
Output: 6014473668

Example 3:

Input: 3558 520852472 656430899 848996621 923212344 624101675 476165397 91243942 194641486 653208422 879813396 809651074 943476467 121619559 149182384 988211046 252952536 394765971 333716828 107248014 127061298 799634373 605572341 746378831 501306968 832945986 86850704 509425279 72931311 929603197 140530996 996216589 30532920 440383584 406399947 111002254 603197133 575094748 410088084 96542142 496767208 579948730 505453472 182330661 791790026 922702809 204992910 312045680 718172615 42774140 191969098 771552655 249109142 760326516 737020228 582770335 336734307 881987032 517452139 138670508 253217898 542384043 172957619 40388663 753517107 938942516 485480417 84120321 161244837 759123414 620518415 291491080 812683716 702753764 318126425 369023726 94429481 110740960 939150846 291286851 788546347 7220…
Output: 8232584952

Constraints:

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

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