CT61818

Envoy's Ledger of marks

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The dispatch writer Envoy has been asked to optimize the storeroom layout. On the desk lies a long table of marks 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: 3446 904473754 475629196 70422515 738976578 138104596 156739789 109813374 513323742 786033014 297080883 467301228 73022046 778387235 225247383 788057474 429494266 737235112 451953787 295299812 316880028 719852409 341263191 70642866 239958484 741073897 884558754 959895637 811802488 323158286 457906271 655004157 396692749 931657565 238683971 126453516 887824521 123972317 922882985 122889095 365275943 90032440 61398270 71867443 978333531 931073604 106743183 793681843 875282250 429108825 688963117 86181767 291009673 151306097 730542984 674320835 737099284 767799107 462612900 111786010 761576657 991043437 584344323 320176318 718599081 524197937 753890338 539271528 736502878 906939787 596706268 73042985 452686904 777756256 832971287 189982010 658261310 755139370 762721699 216417600 437776719 425…
Output: 9047529880

Example 2:

Input: 609 356681023 955028417 88355418 486615407 569613115 103638476 880406481 47643966 995852229 780292807 258954533 828606271 225814870 522520584 835835434 961714109 598486851 124900303 647886933 968959036 139669434 933308376 838844458 139294032 362412355 849006369 303562400 186013009 710907356 442539985 310152659 88270654 373309978 268581053 100587878 33690596 138201983 655667802 181360954 52198652 14451643 32780753 652896976 424452693 745800110 431662296 984881220 643693069 264266789 473529738 457513694 763543429 671527393 369975633 315098513 814846985 705739478 178398242 736109894 900184547 465539420 411374657 617342921 799191780 719035777 139838849 971939118 896226446 556218836 727998880 262125030 268712288 768763748 782197877 899561860 129147423 184596032 721489300 205871879 63310365 8730…
Output: 8544073450

Example 3:

Input: 1541 171215390 414844379 973932076 19088946 592759573 64475780 995775966 268703200 370809138 511557563 782143281 573157241 114965318 212881120 531625485 311985366 883300089 366316435 259135290 357093616 619401791 362166040 382089632 873415899 690265409 86474951 868060846 698434608 362554486 270812377 503840349 525314976 677161130 570026294 144759899 757095492 139334852 706003159 366586500 401503287 827252128 167331315 813832138 363776713 934426701 998265409 136219631 87477756 781439023 476525661 571353793 541505940 172051498 208177497 739984797 799069355 806129448 600197405 930599810 213933299 670999715 688427863 294753178 204581076 653000962 938840026 753964107 171754153 116357926 570097179 137193566 448621814 615980581 916419434 548449632 646483092 559334936 657619241 797379915 157743084…
Output: 9944619365

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Envoy's Ledger of marks - MEDIUM Coding Problem | CodeTikki