CT60919

Omkar's Bronze signals

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Omkar the log keeper watches over the quays of Driftwood's stores of signals. A careful computation stands between order and chaos. 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: 412 435780232 689493239 772558539 297741451 142924407 83778004 945362466 34296501 98924521 151182196 611563773 477624245 825865460 342166363 89212810 462137496 849086495 646388615 169582199 372566338 552864209 966972325 432784064 11128159 149939788 255203768 890433543 643032127 493265319 217432514 402092991 281206240 894322223 591489702 892142973 109373899 730726347 90851097 841756188 187411681 594710727 861291975 389028793 723595427 575561144 477557129 703434087 102777562 102014853 652925894 741994747 598469672 299134969 370884478 899786138 349595956 153135917 33766813 516796640 638517113 453176633 678573613 34259818 504106874 310866678 442250968 403387845 242940750 314689693 393332158 936166131 504778174 648553285 549028440 863558362 971272516 754809210 332501385 801523050 610174438 6902…
Output: 5564974847

Example 2:

Input: 1450 457203682 900241765 957016530 310629180 269413837 628987536 926175568 645595485 378531787 245223648 471242488 518877888 647786299 103262465 25477052 979243014 886271164 319658771 163465546 50108214 887477180 400081708 796553291 483692232 643565531 533795496 561211769 572441370 453043273 159191828 766671671 152700996 72345093 287650549 321858737 318651092 922606339 584643908 649588788 18363849 605769753 339512414 272376804 568686521 954801848 922697856 141281449 700082454 67771580 768602035 934702432 60514784 745060627 895620402 389426453 397707461 884322953 101097475 222602087 399001130 793084907 802109442 273100809 635113976 764559301 541474269 835777421 16833740 903988177 846687091 141582813 114550554 575147317 25054128 675629290 612823121 183558044 415115112 317049371 35531382 5313…
Output: 9285029706

Example 3:

Input: 1547 732449050 778791078 950988381 363059826 197460595 582256416 420193834 326167461 777878085 854378141 587133639 592750035 338580244 810184538 880672873 570498225 578125786 969650111 268393160 933908929 760542332 971832290 335788331 502319925 553102281 972031435 838958135 901975305 254392567 196020251 440608134 201912081 315431574 509709559 669995452 438509224 885692429 947138790 797436280 334091451 729224786 439171501 289731978 505894294 960617969 502395380 737862689 858387363 156493638 560565507 155854163 266368439 31874414 377636136 480567253 234720414 738560845 237494939 47666774 180509171 26954958 835793684 734530136 523326558 817676794 410333533 398911991 59091073 93856859 283230116 27321226 965657392 219211656 242768221 563949040 996316097 916478758 922569861 516390484 964016942 5…
Output: 9408972048

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Omkar's Bronze signals - MEDIUM Coding Problem | CodeTikki