CT59526

Jessa's Ledger of beacons

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Jessa found an old ledger of beacons in the ropewalk attic at the frontier camp of Duskwood. The margin notes pose a precise question. 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: 1384 279146274 406779338 233502096 858644294 58204975 177935916 539515719 867828182 973182029 584213358 223008983 920047462 9581922 281375333 30688587 660083756 718266598 114534160 577263053 801471571 985468695 926580921 162653533 508870704 936350125 603492440 226451007 492107787 878949423 211902182 732961349 297238934 621766363 452945010 838868279 227534709 192532358 118878371 547437561 628413710 448951235 777105804 918111553 941495773 173709801 412543163 950737658 877988785 821647994 664431876 292964095 907000747 342989417 479509122 158742758 968427807 630253987 986986594 668508908 918024712 105185504 922730686 951536284 105987374 107214556 494137068 176949897 668652208 407500027 599351134 417122852 667598920 950091447 245447469 889253126 799379036 496102070 326650816 599101789 832577612…
Output: 7263038601

Example 2:

Input: 1284 606584756 876500233 32897253 539931921 113780972 118853372 789170495 79823477 370457839 102066019 799922847 550165682 477713361 553780726 383274060 513909803 958868419 865600134 224509393 806749935 90094156 212406399 331629469 69161844 578417111 268085205 739116879 232412187 710069572 324047106 67484755 655968979 156575403 904578648 621292371 810995729 776352566 767825525 807032602 769048317 131425626 989626796 426609690 22287099 50379547 423272847 336037455 112026366 724306968 380376823 325294968 983525869 912503388 804166095 52439220 454372417 577615712 740080303 218171870 890576993 641348023 170343194 135232141 71011328 779685082 444278334 681889404 633658587 479619270 722896294 397008162 310507064 192136114 883897306 968825836 77114940 171546642 332187426 618814728 63057455 527677…
Output: 9088547400

Example 3:

Input: 1588 748979083 173610314 194059836 683061560 241869510 914685361 288656154 922365629 391773492 176287306 801281305 57956833 918088736 55274224 779142901 397887932 77202828 466619087 306872480 177502122 62604668 66723193 582515722 456824164 615527938 328041948 17631644 429395525 359227304 857361024 908302559 723963648 959743015 83474322 501306325 907761362 919205876 270117900 349069320 475819011 428241012 185835371 755506605 841084831 819525323 174326680 590974501 899089057 576573499 672588298 88616277 923713839 687147884 17280611 616337222 45358231 847739151 251527935 317124066 607692561 456276579 156678305 113236769 693809589 70736890 86721835 871737444 444722188 232429498 36188465 937885094 141112544 636840199 839921504 654680923 854247908 286732765 620281217 157853664 285578338 13102413…
Output: 7640611245

Constraints:

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

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