CT60507

The Sunlit marks of Sage

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Every season at the otter slides of Sleekwater, someone must settle a dispute between crews. This year the task falls to Sage, armed only with the marks register. 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: 1146 41329581 415895764 29500149 13181509 926014269 454502684 552707924 932521303 176339817 305371517 40525480 905172251 511026115 505714387 938531602 924598590 245355832 501396665 581085361 270059251 359530125 342910688 335657253 221825272 278654854 580713783 278017242 450698693 850417833 701947809 297077522 775052298 442174124 333489330 218248493 875280859 247562354 729949688 584932587 859611635 947251974 603193013 983927205 875204035 471637385 36322526 174233220 352274538 545721498 235949313 908847790 860500652 551310994 695111664 365217581 608081383 261331705 498574694 256470579 198973242 316982145 509779461 235467615 82564487 522350086 891759069 25792294 52145461 303694885 611573177 569457137 777822040 481863451 222448232 953326003 196943765 963481977 167366604 220497375 108113231 828…
Output: 7849865725

Example 2:

Input: 2397 706079848 454589457 880307637 838231606 246062062 388330407 641422255 846030054 834230427 820596859 540186838 791762821 969322736 96680830 233475957 931563383 484174127 924394259 321302544 278525517 535735037 371847449 783728041 949927912 236581214 939242657 22007672 147937624 132362786 701598041 257338838 304856052 955341491 281131066 288545074 915428643 727565163 301169407 462961918 442724895 287585231 357293929 275298123 359778053 310750645 644984776 416452356 306086386 757870139 395404348 180198962 996472456 908801313 99347933 161720539 968804164 189743208 31755098 196136008 292491160 850738128 412768950 836755147 441318559 124615279 17019194 101102173 364354151 583795833 780130816 283259355 6795361 993060324 28151940 156437097 436810027 818452441 120711770 42384367 254961083 7190…
Output: 8266790594

Example 3:

Input: 1762 560571298 411495676 172675689 964760873 666775618 127641814 570093148 563097738 246983218 441061840 342631782 563517620 845562143 35750793 669893879 404393767 123414235 425821651 675511994 419532652 875518623 19866380 157971444 871486487 679712808 509409050 934822295 56073539 278867885 638938317 499198944 362985404 636763960 884188145 880611872 743338423 42258769 813300247 488707327 992542119 349226504 792607249 193617871 750982675 177942025 828618010 223759450 999753393 740073259 142256542 322549106 363368082 560105997 200671731 77153607 665545537 666515306 171464468 960176958 233899453 99971922 987406589 509723548 398978111 64857176 820515816 249512684 379024802 529430164 584055410 464063434 346221309 350256046 21878843 530104230 952806014 46089292 123304218 692338435 711862354 5441…
Output: 7113844400

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Sunlit marks of Sage - MEDIUM Coding Problem | CodeTikki