CT63525

Jeweler and the Topaz registers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the beacon hill of Lantern Tor, Jeweler records each registers 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: 3351 912497314 688457789 816180409 821542780 912335576 791226329 808645893 501974777 946031959 657109466 98727159 733391802 390525859 355700363 294059804 895753105 373509090 236576667 840347484 626952284 937094789 270186937 931170662 871480423 926326450 877978909 353168855 490477574 29484794 931708049 100522983 777608676 751110765 824102923 899781510 731439954 216899312 525507796 51898286 716555812 466959271 552411115 505722889 834194043 61317688 147089320 507975684 360631577 136446281 150587504 902761193 323028496 602858329 973861572 19449036 776914038 531842331 77679245 334194403 863852484 672531046 28431370 615143234 798526122 69226727 66647323 207213912 798317396 151374190 423917702 732225005 469931348 819889564 273787261 642332473 271288672 210151088 266139512 753763567 646074503 2901…
Output: 6443098050

Example 2:

Input: 1620 513784352 418593987 451934303 195018291 377901380 989574422 867286519 820387565 938715911 870691875 576856604 990430913 24853571 480817229 253881406 246174162 445569240 975469167 913766606 899682657 316590107 262738953 852866525 472710342 341612061 63096462 365164289 278567664 473168442 349551865 639201881 503939793 405693385 645989190 289090211 385691275 97163438 172803314 170837507 897608306 12577835 610419649 607180321 709092944 994745020 319521754 461858567 402248254 501887869 712190724 724288727 583008022 687121066 529182973 775288035 360186112 358793937 510470715 526800807 989338466 879659897 141508654 628868570 302873938 335323451 534733046 437688136 116360452 643028257 732644811 953673603 863797390 301015117 622837181 784292705 24048959 769898825 9802213 982943576 184269194 16…
Output: 6390435080

Example 3:

Input: 426 259677030 138190320 377602983 413854027 415437003 412002959 518822105 566347771 905909959 827621229 697956736 299901690 463756295 386322013 851424919 785757577 90113350 478538420 992575391 142719117 427862145 550498179 619017063 996272148 157568440 245768498 365749111 191971276 114561980 762436371 413564294 397850870 931374663 529036545 446951896 380750324 699535885 772036333 859650745 659543258 466027424 357539279 795702409 633977022 143634269 825954643 274005121 598888642 583502926 960287530 421356255 561826004 125095750 425613306 498057172 12881734 301512056 640831826 691395205 497629662 601300390 472818914 247119558 149948353 575160570 930563134 607791771 453213069 464143287 92367580 891839752 722747340 920705096 323987402 206371778 50017273 972684218 785711924 796890159 955466079 …
Output: 5363089185

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Jeweler and the Topaz registers - MEDIUM Coding Problem | CodeTikki