CT61891

The Scriptoria Grand Facade

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the ink district of Scriptoria, Hans records each ledgers in a worn leather ledger. The guild wants answers, not guesses. 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: 1934 83888555 869886383 692612927 779476848 233760579 941086499 460854323 20182963 795534362 966346405 173844790 318023322 99900494 358837767 586675835 375287548 552237395 669934186 521117669 406751965 663805164 583320742 407375858 575108664 12002441 323215769 166551832 24641528 389630402 874961481 27151481 733495407 116963617 860316344 748603230 24638612 962802707 957600944 922940716 889433288 540907682 966782623 72886399 952935670 524742142 258544585 382358386 415478626 914813369 265156839 730134215 428056005 830099039 501682071 509085380 686705470 906919942 24700938 280204591 380096151 424296761 741742530 64296458 15713321 124327151 788224127 691134348 431338882 608179145 555325178 534419789 766715627 840624319 86538981 611877352 321156227 517831858 222752997 579602922 909074680 8085305…
Output: 8056752210

Example 2:

Input: 1806 219278894 521597816 263280870 637840524 590913164 494357404 542879929 165874882 707143713 406560880 332387116 475844675 119927591 893807987 51670703 867785768 948422415 915915465 272457760 855776726 104019859 612572555 233999232 58550398 481575514 553037727 468621554 112211820 289215311 124719647 934237495 358789018 424753701 440931779 382871633 310430614 36268398 137980003 765764031 402513798 305461546 634336803 834355004 597010379 565276967 815308673 551441533 459534136 830235278 777790140 590445066 222433586 952143740 346155052 576105131 468952750 289408525 298660911 979123242 377650223 240337635 979599001 171026458 701755603 165221803 217212052 376435283 146357615 703369054 714473673 662187101 620602062 743511094 406964760 574460083 858025987 962588591 867568329 35404394 902125416…
Output: 9123388704

Example 3:

Input: 2728 388299246 595959036 584079528 621252835 872158584 329559841 1438406 349396930 544802215 369460993 527995702 628266778 391974220 695023993 569334164 647891077 171252446 42808429 327515388 497352561 159551030 156675757 911442745 694677391 837889795 640930959 938185002 869798034 959342997 41086522 667484693 713138501 957287554 388403543 502619042 653308405 15540286 331388197 260063774 801749025 79990125 914490223 252197517 621856881 520156084 568102785 421588564 646455767 49892065 305105675 978516213 881074185 388922065 722199794 983646425 580791836 563525968 487640013 26584779 817305085 473723962 576971280 481095507 350367591 819706899 919516359 292579817 183216667 565195918 141550045 887501913 982108780 970635353 653987234 402375088 969689979 524762344 494497987 573001206 656645517 980…
Output: 9728587200

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Scriptoria Grand Facade - MEDIUM Coding Problem | CodeTikki