CT57362

Zoya's ledgers Grand Facade

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The reckoner Zoya has been asked to verify the safety inspections. On the desk lies a long table of ledgers 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: 2688 770209307 499906127 744922765 980242615 833933255 752898803 944646521 493573244 285367071 3164463 506905677 517831878 823778404 757462503 221463504 887195207 712917218 706817016 743118023 95350420 819960353 750117672 265798080 710226238 316289893 720852019 207608173 173853759 824558275 948946382 463070805 274869248 963781410 89302665 832397978 47084500 90418255 68794679 473113147 228314680 637715772 564148165 156393730 528518134 35688710 520629688 76073441 862927421 229297435 222286593 456207495 984021440 444699444 341677299 692325142 338994789 892787226 871044717 12637681 317123231 31024804 221529014 37245774 514937081 857988076 500218144 798715380 956987954 416768131 504668107 529954659 130230108 167589472 690382945 425770321 948252106 358348786 433159652 666316181 572299476 1562043…
Output: 7378373898

Example 2:

Input: 1976 284464431 430878249 360689810 171664563 199538419 23928847 268710914 791990841 819615991 834842906 987383185 154959006 732622109 642556759 916619904 592553636 113864806 838467358 379832548 462139676 197185125 673927394 388623010 382516175 154433421 616841372 574251329 325613594 656524937 400350596 195807329 576962277 37957081 392359177 847713761 902290728 735827408 724126794 160809571 230526557 515019314 112242129 292155538 573386485 850398552 872686690 318456580 708112373 377609225 575522454 712972475 276861 104458992 541900552 178316121 803612069 240088872 53604147 194218038 888788825 596620831 543709406 969281233 661792839 133943744 903451191 589589906 637872038 66467322 725959294 502692318 600443484 37381346 680077849 944846295 546614237 620476570 669384012 34243969 390169780 4207…
Output: 8224986472

Example 3:

Input: 3443 641259769 561838384 365700432 949301169 378354726 333956807 324589216 619898855 186224524 237681573 486872787 169627134 999502874 547421540 891053311 751894426 16259309 910169309 957736074 659846627 976364114 436142819 742426146 472002795 206297023 253237943 54150806 721222294 473107153 680855311 252398880 668660830 362133188 882720891 89404360 806955987 765093335 287340265 363189350 173135721 531148757 319642301 444712466 802265534 427167653 240221097 492332648 76769834 675909134 840128543 636864976 245205861 389816065 616354279 706492037 599460207 837627892 845153933 47875671 334762363 355767515 986889214 993565178 546763037 697340703 269802917 352986369 263444736 45817436 850653731 395238105 424073823 601148582 486231092 953792188 707073493 494178283 157867551 561323754 899253302 2…
Output: 6699000360

Constraints:

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

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