CT64502

Seth's ledgers Grand Facade

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Seth runs the shed at the old quarter of Brasshaven. Today the books show a list of ledgers, and the numbers must be worked out before sundown. 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: 3276 24760573 990650703 451871653 262084920 6039825 406144148 524269589 354625203 512301339 944680103 514667172 594353161 928179696 932730054 626416298 503084042 119178670 589813913 150240623 832230218 852994336 453986157 725452355 841567215 631565194 377049409 551885771 836272312 777007114 851793552 954110002 793624262 781640198 765977787 291289370 584592109 312434529 20548202 486051527 546522067 916768924 123402619 643292781 108621469 821306275 139959397 154181363 981213533 113944135 566293289 304665849 864573638 673713262 434833294 765735376 255791929 192112556 497464235 338472807 248744493 272543785 492912350 826057522 779491546 662412794 569181879 622356255 452930956 849990772 148707496 48596956 928177307 503237867 591895675 931473285 360700918 618339999 967964039 924763734 584221525 …
Output: 9210157476

Example 2:

Input: 1811 151186525 912093434 251447059 871071925 848081943 650063227 846323388 937542230 814972720 882867077 939162195 726163207 259341926 19939959 989667346 137959479 504269546 894875731 390955863 350241217 907253503 76381356 94591103 372562268 258042817 417864641 721853138 352195944 332348144 972575609 198260197 581197546 567096789 781102506 291697129 810526844 580963740 847264417 628393153 521091256 182409418 629670341 952309166 501337886 293954236 963219975 270378062 810875203 622474751 982471386 182006049 163152890 149950698 567167334 762807210 368734186 90765323 876257713 323686302 219432455 834361196 381195872 7263296 227032819 808072659 908250459 438930215 226004243 176084906 858454243 132005085 310646305 67091584 464032616 3380440 969766893 342757322 65568497 804310081 998669307 67734…
Output: 6402460412

Example 3:

Input: 2548 162763818 568627338 144219655 296074015 766118619 44002370 487604255 868514420 940076679 199025915 784587124 620080995 634506553 898698410 278675342 606049051 252144825 989892267 530385984 421671121 250464759 291179658 532827675 526677406 927358097 755626028 218340510 931936910 517623516 304711439 627715811 260545521 253206314 723857268 244716959 170527899 585506310 939809075 503756654 681581198 920915099 482102270 863133321 305525029 133106764 730593194 117975513 61887263 238346109 165237554 256333749 474834741 328045464 424035182 36775159 569668474 300295744 434546806 688283219 505548455 989011810 727773242 293150573 998113991 288110385 760526968 59887514 410502826 767695477 934039242 369650048 625113021 35860090 400587329 370961733 15719808 732348730 132226834 171348019 80247013 19…
Output: 10819705724

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Seth's ledgers Grand Facade - MEDIUM Coding Problem | CodeTikki