CT65266

Kael's beacons Reckoning

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The scribe Kael has been asked to prepare the expedition manifest. 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: 1649 745419001 839032360 683945523 499695392 679124901 491998707 924886613 689164071 690312681 297380236 240848033 982631742 377199608 389820258 109451843 897553249 802009987 812743204 792581156 182172819 526719964 292819011 252774888 851087126 287191750 580898995 674246014 548571990 723561304 508354715 388545015 64604721 769438800 809702785 200050956 818377580 73593399 935206783 21025420 595220419 77139494 950122112 11501545 488814157 825628913 542192701 773363970 707035280 763101621 506149351 567801754 517073090 816593754 264777007 835773999 730592174 733635627 306605083 908749926 609871909 490700980 557711988 435640968 297005188 263196566 989622278 401539210 497036858 371802497 980146868 917242406 455111425 965217123 817732681 398357770 416149660 952911660 260052850 768485513 72688085 9…
Output: 9636555222

Example 2:

Input: 2965 74891577 153063203 686199066 487495574 139781891 669074344 70304284 107866005 925373386 218907225 478035924 184043751 804139624 666256355 112529203 140203887 813768820 289039836 75577398 404952603 621684845 399690555 861837804 257549089 361551062 837208426 620213825 554152274 34586761 434618856 531599074 921547425 617594665 593525623 20833391 372344791 115449135 671557544 724140445 576734109 790896672 136712733 438042521 842662794 902415134 945429814 788565008 82643052 558026885 132845085 885082962 36657969 243404740 573420313 979143439 283903996 883916393 387649212 513684695 907757721 662747459 550045229 116395741 993616477 603257535 473251807 378229800 669047304 506316027 326817909 968667438 486230498 863188529 856120048 381046535 275846138 226427949 347187490 709662467 849846389 61…
Output: 7343346904

Example 3:

Input: 1089 697021820 237641487 874103615 471429444 346528529 639708173 120709787 269498002 40521683 773755873 61248316 662936757 274711272 207843595 352859157 541703908 429777398 970022350 269955431 406124543 727025373 215861770 889474113 561883558 9763313 376724417 117424081 523023722 579352689 611772858 734733640 966927402 708076755 656079020 815548894 984834036 569182274 348391902 223125454 493843479 73222023 769858491 301519790 657850170 118701412 872633690 839809678 501496920 82361468 958253919 781086419 811618471 764106318 114344806 62265558 324523258 368487581 799019162 463596897 810906918 747055882 851573186 207657869 645519552 246989755 295925004 635682185 227350594 227453446 747275373 863620491 150656826 762146066 645593228 818380246 877380241 415316362 43497016 951332164 175046581 647…
Output: 6072079200

Constraints:

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

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