CT60866

The segments at Thornveld

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Every season at the acacia flats of Thornveld, someone must track the breeding season. This year the task falls to Alaric, armed only with the segments register. Task: Heights a[i] form a skyline; after rain, water rests between higher bars. Print the total trapped water. Input format: First line: n. Second line: n nonnegative integers. Output format: Print the trapped water volume (fits 64-bit). Constraints: 1 <= n <= 2968; 0 <= a[i] <= 1000000000.

Example 1:

Input: 2187 198569043 465692037 275828493 421769493 659280058 290027655 755983595 486707469 441119382 883926125 240393040 221667328 358239070 245527638 467128779 809596561 171575251 17181503 611145901 677096663 908843161 862772191 220464710 166412202 328026839 79983158 930590188 798370290 899522325 722269511 211790524 820204981 266814724 506198178 677976617 214946723 584339780 224492047 305197706 740588466 345889707 302113274 252832005 1667120 999494737 173529830 231470904 997043882 465013903 651082015 91242746 405432970 905236818 72461483 594372285 32530525 691451172 738117939 358189193 189413284 756078890 934385446 656916845 308873910 642707107 874918314 630159807 942976859 917370838 770408935 926169126 118289722 973732592 811293186 787557918 78283558 761225465 855685670 606703372 748346445 747…
Output: 1091987187712

Example 2:

Input: 1508 359299736 729127515 203313473 195879291 992311426 546734025 92940348 195327499 166957358 823347751 164318882 573567782 476448744 78156570 143952367 12884010 202195460 529489871 484159561 311327822 709517332 151472989 452754434 153720983 153971488 79193002 521115861 952948746 752589427 390751752 784327957 321232054 44233669 726921691 296850631 597878760 947382706 303637745 664586135 955166053 107420464 785156022 832168775 873046730 249115116 379999391 499283000 933881371 155859706 433600276 201872794 261468798 103385886 576636942 742078926 143247661 656008386 570336259 237298565 808715220 105638456 146918295 59831534 544096953 710745757 632377876 746046068 893866019 218599993 512763255 948060030 842055998 910309563 196996866 233714022 30635570 70186419 478924203 894522163 519276440 785…
Output: 735910156636

Example 3:

Input: 598 507392367 647810555 262010276 510034742 786432131 440242487 801064027 615186672 951119677 940173021 629446126 477049059 407323093 995629285 224778381 536253265 189011010 599474456 132544286 653082319 442228433 970334793 624642690 51061438 104457075 459701854 466283822 989887086 810320550 811178902 970696079 243257068 708850228 996177195 721829300 271014319 689829007 494795545 264838222 873757901 890929246 290487528 794717018 518308357 595889908 634218788 286100244 826390237 300985626 595063918 236198923 586564237 212141176 280210434 679036983 742509813 92279686 255963069 646046018 575801461 341451950 668964637 962599235 16656144 436226066 500106667 310381288 924449367 975137678 177362643 495072241 160762991 415961816 822448435 929643461 740190063 383605693 569719533 307793124 912136970…
Output: 289481076111

Constraints:

1 <= n <= 2968; 0 <= a[i] <= 1000000000.

Loading...
Test Cases:No test cases
No test cases available.
The segments at Thornveld - MEDIUM Coding Problem | CodeTikki