CT57413

Last signals of Quin

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Caravans arrive at the railway depot of Cinderline with crates of signals, and Quin the tallyman 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: 2861 978497490 758249121 646972979 434957168 394323403 155112648 627768435 810376438 404118919 958173867 815895400 69926381 430557362 51461408 405436447 852276639 514852789 383751161 84137670 209734473 33755812 612284448 339863708 271592481 171177801 956489734 501497907 537167196 534468662 650607910 829937793 376659990 245187668 34436164 430300253 249853874 821976883 308365580 974900028 251458436 592988824 441756915 25616023 693303875 320626838 249342430 92618526 34998627 926004924 95313802 923235738 512546742 955632486 958930424 495059359 83404328 273438030 125875569 220043778 808630560 189464089 289456646 779927526 87848299 47391142 315099862 439803781 473867272 61830714 747048260 602527298 35472925 184342553 914677046 621870201 643087673 139954125 870412337 173389037 2847632 219415520 7…
Output: 10026986752

Example 2:

Input: 2108 64829821 875312856 481674440 785367421 834038547 515506204 474405414 862341988 77948180 692840582 459961937 717278284 860676281 347047822 458168103 402407260 656744086 47234796 664903089 562591483 881700882 991204886 296845437 718102142 461646681 76972160 676379316 173529522 108080374 220837130 593177439 735872290 651516520 939805230 796911381 559088322 330933462 482513320 926767871 571914866 64395298 798797217 287096447 211836136 725002273 289650159 820884260 224617194 6328969 345139628 146569543 514689399 926615640 190857880 869905368 629110860 653672914 482661017 370935796 910459515 134409037 619379618 245271427 957851554 996203854 904204405 80175088 989309900 687339191 986474902 589665766 288671993 347744176 580555942 219552931 560301411 342637106 692593696 579594728 713823188 264…
Output: 6542417504

Example 3:

Input: 1903 139344165 667770491 961976270 111192239 635450640 90698183 62835259 176525181 564561653 776370421 570905123 49031393 162743634 779154018 109661777 722216692 311074282 238940527 819160526 747442593 360121139 10049308 365235414 726921412 188762132 512824757 688558301 608750491 386276612 181898692 399196652 52841357 368491286 46779437 192515974 587347804 283582462 316432050 24990537 215079857 282709958 698012837 725411247 303244172 28934442 673666964 287667369 593394084 116452467 963622057 873408999 160703294 956177645 167050110 991148134 840829283 189395020 221703141 383011252 671896511 525219479 226858269 726404547 771514184 409034385 852774890 568358811 414244599 584735206 796578972 331159463 388043292 434974822 738623911 563920533 659697389 552077718 28368250 707962373 248931085 2152…
Output: 6638370836

Constraints:

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

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