CT54634

Last segments of Jaya

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Jaya runs the chandlery at the coastal hub of Tidewater. Today the books show a list of segments, and the numbers must be worked out before sundown. 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 <= 1642; 0 <= a[i] <= 1000.

Example 1:

Input: 154 726 187 366 572 402 564 225 113 766 63 118 832 272 256 75 897 18 537 655 996 313 489 428 13 269 174 482 925 131 348 513 815 361 689 325 155 15 660 310 960 612 848 165 53 447 415 991 364 909 265 489 161 705 191 161 997 120 573 840 832 354 842 545 366 807 424 590 470 583 219 177 98 82 318 217 329 467 574 849 207 779 337 105 956 47 808 558 297 455 455 695 549 7 907 100 553 782 266 4 496 468 125 825 125 299 873 273 475 542 415 779 991 872 165 439 642 431 171 294 645 221 229 514 895 93 387 647 543 137 714 846 711 600 655 945 858 498 649 230 829 229 732 684 506 941 354 740 994 627 875 479 592 861 696
Output: 73165

Example 2:

Input: 1046 497 286 961 585 134 916 820 751 550 646 442 450 515 337 385 69 538 845 507 929 599 685 758 512 721 357 816 722 645 304 296 563 361 401 872 392 559 727 70 444 114 160 496 261 988 433 679 319 290 274 748 141 146 685 208 583 550 308 389 38 993 458 211 742 737 204 233 595 283 868 120 403 201 879 337 640 295 739 598 866 194 328 688 247 247 837 857 451 244 885 703 377 353 428 365 323 164 633 538 745 716 376 276 263 20 744 195 529 283 378 411 879 892 932 271 627 517 56 186 842 936 626 665 720 953 918 601 160 969 15 916 100 660 493 475 199 320 911 334 553 287 283 782 250 231 645 919 311 893 513 440 236 592 614 755 488 711 489 693 200 655 818 450 0 98 205 990 649 770 314 880 355 582 998 438 72 549 750 100 101 701 137 24 181 772 35 703 612 912 500 418 924 45 290 991 244 634 950 815 81 682 718 4…
Output: 505330

Example 3:

Input: 1619 733 231 225 304 92 833 989 585 136 89 922 975 223 65 740 732 964 459 599 969 439 374 652 54 122 417 134 600 215 689 878 441 921 783 612 540 863 263 476 113 703 300 127 767 229 675 186 503 130 111 558 622 534 581 470 943 781 965 508 954 924 593 600 686 101 399 718 534 547 564 616 959 431 236 896 384 819 225 237 619 89 673 652 405 736 343 316 699 338 590 811 301 672 325 136 373 336 850 887 523 153 926 522 251 120 925 663 203 343 64 529 646 98 924 374 290 482 292 682 296 849 739 634 440 139 853 371 530 218 576 969 376 61 116 611 380 636 303 157 330 791 308 510 542 752 454 358 193 685 224 462 606 4 222 294 614 350 263 701 23 971 566 122 434 479 260 684 846 565 134 491 856 399 890 236 926 492 458 421 664 381 811 483 230 567 396 999 594 254 987 138 436 426 776 675 171 56 66 205 389 237 598 …
Output: 800289

Constraints:

1 <= n <= 1642; 0 <= a[i] <= 1000.

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