CT46705

The Silent segments of Sona

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

It is audit day at the terraced vines of Grapehollow. Sona spreads the segments records across the table and picks up a sharp pencil. 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 <= 1473; 0 <= a[i] <= 1000000.

Example 1:

Input: 406 510962 75539 626982 870194 837657 397098 397728 507411 854060 526499 713901 335251 38426 834072 427086 503713 105901 155379 55063 347221 857222 215468 954137 944339 872309 543957 532949 739645 691580 757171 868945 126591 463639 158814 141902 590109 724545 950303 660322 300378 817435 784738 505653 96938 947817 653433 361985 296264 610755 541342 835918 490300 499456 731998 8117 190142 946377 901266 74916 991115 157126 307520 595587 342880 783008 825885 30118 194863 775718 849758 392376 859714 494383 768405 291562 608482 298869 864880 87568 972548 20237 717543 207137 162403 628427 859788 113168 38974 863054 431983 462082 859517 33938 557945 746556 739574 811769 841772 498617 590868 901707 699892 748043 471455 37867 392978 271547 433420 165630 156112 64935 149707 389252 347310 708104 40366…
Output: 189725017

Example 2:

Input: 725 43898 948306 472055 298319 195848 400281 969747 699098 24067 496208 553809 600204 424356 444659 587928 121536 785942 493293 426647 668249 390857 860674 943752 339576 3440 80898 424811 560613 608736 769013 530011 124070 423520 987477 506386 506811 612744 765864 621715 64930 340016 616337 850346 216716 534626 947014 441900 909080 242906 505078 757322 996096 602262 308704 376751 540632 78859 582069 929254 923877 891757 482974 587272 749226 737867 357793 954618 785331 866622 990127 776956 330071 383814 374103 948857 428578 588161 119868 174943 644328 905569 691721 149338 860097 516072 627376 493373 829913 853776 816946 607132 161517 962741 953932 392292 829221 962895 634229 505357 712792 487974 812349 18314 861506 207403 367990 511462 174982 553026 182142 781138 21672 300656 77000 179406 3…
Output: 347496440

Example 3:

Input: 906 200906 190953 805631 673272 154757 529345 864431 361042 487722 956600 882537 949941 566860 337709 686309 96520 767343 948504 830934 976632 729236 21276 377270 561620 433920 190208 69639 346083 96409 466085 55149 885499 657350 50893 729212 615345 183986 179317 958410 438978 730572 216231 289250 99587 955717 925669 626482 520266 422237 532202 741408 977867 31211 226666 260626 871635 232100 247561 902344 242051 513554 907765 575095 606530 953901 747576 567218 412606 318046 904434 202194 751335 735853 933259 665217 123041 380876 497300 840263 111643 393129 193413 102863 257631 414047 140977 428190 942765 228614 164476 956640 162113 867055 967602 627416 531210 60442 65914 817739 472740 548323 45002 132307 938377 813721 526460 688317 772131 105525 252989 681639 52844 6688 213297 706378 80208…
Output: 443130901

Constraints:

1 <= n <= 1473; 0 <= a[i] <= 1000000.

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