CT61143

The Grand Facade of the Tempest ledgers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Emeric inherited the customs house at the steppe camp of Horselord Plains along with its curious bookkeeping system for ledgers. Time to make sense of it. 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: 273 192898087 499768876 256678972 255922126 731302392 679355767 63817543 190852903 362315099 646501626 898666210 659092823 306224910 480047068 978339167 792094282 946969854 984672509 447633290 260396294 908914474 70074505 433671248 765571114 144178005 177099279 991076622 317313362 320869255 406924520 694007312 293182230 782232130 421119006 598838693 446625792 557453893 228768043 812013602 220823610 184272642 95856874 524497179 246931436 415390129 282698524 74599648 216915920 39052294 286153735 348587306 800784620 675138198 442486509 674437623 900512918 860864870 514464355 878676086 126951168 704651861 636576998 487212085 705077226 682787054 239384628 427360616 336394520 486320395 556011646 337845661 376779668 121635654 941912643 202867096 804170437 740708721 166610609 197623879 189079859 5…
Output: 6689960970

Example 2:

Input: 1384 982741248 575693907 542219174 347515152 398337090 451776150 907293566 527708919 332079782 84456614 458341268 306009105 333691741 253871798 885572210 85897989 555690169 198171146 334687435 475904976 61192381 701891633 634975079 160972189 149388485 521099055 556547700 645996597 5815994 409133284 121202913 238632790 931991513 175754408 177968368 600959440 25975750 247623964 617387670 118654062 914994506 667765458 151234806 422043325 661242818 19795475 175160181 921527735 489478918 11091982 48897927 925545216 527789805 423023722 73462978 534979590 988672764 482302370 967262310 516016131 571545011 583776485 495848276 344279242 146759590 227925770 793539385 325529415 999339653 531500272 421670709 364327140 476756217 790247794 191711526 514955488 194045059 514731736 504193097 212504018 43987…
Output: 8263869691

Example 3:

Input: 253 44800242 523005826 89997623 472847319 505356336 92704099 791361429 863514448 165249045 567922983 705011931 889905668 694303175 981390656 292841326 510488180 107582407 293521711 66382222 349720818 656753960 489146434 675047683 644777914 173209568 27021474 295242537 325706742 939029818 975720809 397203049 3755743 436272720 845935506 814006050 529177481 960408639 962138874 994981893 761473597 401963666 931519710 584638381 35459236 965001762 157607162 289900268 298076392 863205971 436876961 768345248 45316493 36042680 993175762 499347046 703873467 783239987 395759424 674519288 641425551 419331894 49221739 258565931 820214427 805987835 8818171 863124304 471503331 548934750 951160065 244976893 600945883 563490812 249086420 636299192 705733219 621760876 230584726 377362039 788589798 370633493…
Output: 5847076222

Constraints:

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

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