CT60796

Lara and the Lunar registers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The scribe Lara has been asked to prove the quality of the harvest. On the desk lies a long table of registers readings. 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: 1974 160932038 977474824 228471574 562280186 960881623 880474922 552526371 673682859 868505459 886299194 320432523 459901397 738927401 771327446 452104621 909217051 219085909 646056130 633793943 139660112 215110821 999928143 457321832 642251733 73242529 708178844 179021561 108654181 734599104 280678000 658432341 497623491 456185448 88608413 819349584 63890445 762460496 35195953 257516013 72756984 516698554 55223491 605661187 900915795 794903762 230144228 671452185 651826758 220306459 870070018 647054346 270682498 127664426 32889136 959587076 819054629 105937342 394634944 532580994 495356835 785371338 944524885 190236903 308023480 49054539 853343928 342347135 945437434 617455562 788415873 101684142 820595900 830450737 408061626 387688853 318168890 303347896 206503664 35579267 140377372 9202…
Output: 7642235760

Example 2:

Input: 161 786928586 254013226 715681275 330964175 489668489 802545438 29011422 979942003 993118341 993581203 13351949 616827105 885335476 728498360 997171482 554716046 878124856 954757271 775460564 854254129 243027815 392694635 17743507 948080534 221815444 730425557 734256183 995976922 33174188 753746752 846676352 469780863 943471250 546892881 392042258 792659308 47835402 52730681 737748268 352145930 67168418 273483854 30198014 164276039 248390788 178335188 549256632 594190762 588616025 855168279 189290863 687091827 289100834 662071048 21986133 901774020 934788578 83963226 845209868 200019979 687840495 387559672 604953482 471209605 938098198 741141389 617282814 494895130 621257297 309506523 855983982 145565953 732919758 27929569 936253760 346661177 255445191 241451325 795641993 293153765 9980382…
Output: 4992444414

Example 3:

Input: 2218 354848039 268644658 58931559 887937224 903890695 88037669 273932942 53874429 227557939 847124037 524261818 381212069 803345 148428528 797340762 47188712 370841138 13067797 400292861 842443893 645875169 586468120 688867014 553186520 562382152 963118846 811553155 80763221 207127465 346227402 907956209 10936378 245762167 547158995 587005189 967526025 545851897 484199600 634487503 489280151 755422065 645350078 856547467 593151669 973983240 754634280 981045192 779726241 567259674 914170928 517567468 795988888 789616462 571989081 868579322 194038612 241853762 878802719 755958604 820766101 859606633 718768426 462871128 389434040 512760334 360114654 479704337 833398181 377250066 285402110 178651255 945272403 5426782 548651090 739228585 558938473 434095233 993217317 398336050 518239826 6962982…
Output: 10652391200

Constraints:

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

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