CT59109

Jace's Azure beacons

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The assayer Jace has been asked to prove the quality of the harvest. On the desk lies a long table of beacons 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: 107 67354912 924264070 10485656 635271819 404364520 164862812 264782981 925767058 816007771 476548468 454537631 435613522 462125157 309702333 59567561 915557109 428761614 22433872 367789735 174264599 596919194 407442159 49969987 761346006 231277559 295223766 910061791 819991573 430877562 860921477 782321520 521207264 624693241 300031947 544615266 707661588 499379185 627474932 184472797 767913810 360580571 297894802 199132156 249767539 500240244 632707042 822666185 423337492 730390288 591856469 926128239 304534682 129542449 329308390 264257906 840790626 431589437 19911548 540830528 829141637 503549596 848941911 373802804 111086979 651736059 990786741 140643249 383520054 66899666 768249175 796626065 200759851 457174767 90069313 363927737 202123031 155258477 625372089 447050302 513680458 6104…
Output: 5349711113

Example 2:

Input: 2597 809348981 987001080 900650134 54912356 651686754 357700083 847094282 91910426 30941785 829350846 743008956 775351853 478625136 714868955 175009485 577756874 141319216 917070339 237473887 850198627 218766645 869456373 718530954 350180406 863225970 635246933 150608857 328353498 729436865 633765825 252780873 595690582 294076593 601992780 922017315 518592380 50360432 774593689 205695616 803478293 878505466 866181189 222447405 991339445 45457044 593882652 391395736 66621491 419190241 52438849 560242550 554217018 957769458 730097679 861792458 30651727 755699505 239205286 257101375 798891524 855469173 640486920 780191225 310767458 239481239 721926308 955090447 292381311 553919490 833700411 830431693 487535174 147804850 510079417 620227549 465609106 253859418 95040519 321710007 648135484 1494…
Output: 7546544460

Example 3:

Input: 2784 413379130 333232507 77920984 608160630 558965395 460475567 450581961 706278137 641185871 707076314 319192244 48184135 769910886 27790000 115039656 401680379 31226510 836630577 10212250 966319512 512721239 6857503 634188360 347365914 901331365 306822179 650811057 289981260 182861374 302740500 200116643 733693389 563423918 15949270 369849076 452143365 737328110 93604174 308481645 818039889 421613820 872266781 481001172 499298938 637072285 880681477 340596088 849663401 8967678 112860440 78570825 737762824 277028450 947911360 733611765 826925961 561718272 195926430 378440683 139827809 175923661 948710860 789488603 935516966 86125738 504826270 183354506 822355358 509989758 514172700 306965329 911475808 884050604 583481368 140616008 382337211 129003839 148956375 281989189 677942097 62182762…
Output: 8269844518

Constraints:

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

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