CT30164

The Frugal Pairs of Selene

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Every season at the moonlit lagoon of Selene, someone must settle a dispute between crews. This year the task falls to Zephyr, armed only with the windows register. Task: Print the number of index pairs (i,j), i<j, with a[i]+a[j] <= k. Input format: First line: n and k. Second line: n integers. Output format: Print the pair count (fits 64-bit). Constraints: 2 <= n <= 2200; 0 <= a[i],k <= 1000000.

Example 1:

Input: 2029 402351 456718 837400 922230 365424 852292 603869 874835 375862 95187 239021 800696 621887 576366 543082 131399 553705 586256 930745 123923 150753 506046 73317 62038 227252 393115 700045 210348 106378 794788 383574 94866 408984 582812 461325 845430 984240 399550 793110 980729 194571 98955 781505 697709 270993 263274 528489 269933 899711 38895 897153 567311 228737 729505 829235 457560 937796 874121 294968 784109 954641 623961 631782 576841 997194 625681 126776 296423 366781 595354 782431 631234 100691 151070 623066 502682 966121 473817 572072 766339 687637 290454 908192 85271 120738 970755 125657 565467 580253 781576 183591 261899 33179 698521 11487 307357 466 173703 401029 101487 879235 512715 541823 168995 261446 155845 942706 778520 586744 435874 82205 863774 934447 999469 546135 555…
Output: 144133

Example 2:

Input: 585 481337 493690 488996 715802 546949 915223 885926 339235 354646 849025 856048 5018 208754 71315 523898 260540 250139 810064 754692 678356 724484 415840 11281 522156 121265 851216 777454 351510 338668 442160 76211 880754 842393 420267 257783 550766 120211 823314 261900 951243 653430 173574 114792 660768 727157 153671 70835 527219 806198 608687 251700 837618 154188 604555 713220 252685 702833 865253 1995 361707 624413 266317 47075 305229 752405 123315 514285 989305 453078 967542 355779 548437 366329 759898 496502 290928 49513 721893 231956 556685 516610 174602 28501 373966 349904 515326 905314 187144 772310 964969 414010 599018 62062 827197 710694 144762 29008 172952 833021 864325 180267 70476 589856 99687 699722 394264 644177 574257 761526 677251 513860 521934 763180 148332 283771 830052…
Output: 18476

Example 3:

Input: 1790 1979860 694980 487636 591419 189654 177496 917586 129690 989922 904967 991287 518969 815030 141304 117907 395891 775647 457170 853608 131604 222708 597619 912700 127465 633528 525876 513141 737736 565879 590018 177287 428914 919257 892239 175132 447154 682439 855084 951513 974817 137837 271599 623802 871398 207297 183844 937018 522039 679642 73982 63831 163915 529919 640981 276765 53024 677907 868433 255487 738690 122517 742289 662278 723404 294499 86744 244485 989868 583209 32900 488796 580160 615474 935731 256919 106567 794340 688655 983171 282309 27884 873207 32022 996705 214991 399185 396869 112042 507825 219739 88933 610691 904254 434260 551385 151585 772241 132305 147315 144217 708639 100463 456785 608408 352059 338621 244625 36790 269175 335707 235609 347137 110952 761655 18095…
Output: 1600537

Constraints:

2 <= n <= 2200; 0 <= a[i],k <= 1000000.

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