CT49023

The Frugal Pairs of Balmcrest

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Chavi found an old ledger of scrolls in the loom house attic at the cedar groves of Balmcrest. The margin notes pose a precise question. 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 <= 3516; 1 <= a[i],k <= 1000000.

Example 1:

Input: 1614 810800 215080 90790 114727 737751 437560 316560 130328 210047 690253 574587 618154 45422 438664 486539 613190 741724 12739 259779 594975 41813 414600 985787 745835 712402 653097 320298 848611 702781 82883 864086 403938 384308 419530 629569 180140 526736 899784 461211 615485 251527 897882 685427 134854 638912 146281 514763 571376 907111 257196 185774 55846 229492 897591 798992 112126 831717 815778 513614 454886 779106 795128 674317 829942 59013 426733 105667 936251 728291 281832 660936 278274 530410 740705 698783 542027 345068 688861 744950 63182 103176 432054 588765 169780 264377 634828 325650 971056 590926 91237 35272 404817 907460 412079 324802 771325 590418 706394 676083 467258 366366 542633 934492 463383 427426 879299 12411 2468 210514 898885 561117 913427 517708 5542 292718 48455…
Output: 439689

Example 2:

Input: 3106 1563203 188915 676237 110151 400691 623104 579937 91947 266012 916985 496270 91229 918926 475897 139490 584043 601570 748936 6073 138294 914612 938838 245418 491753 166885 484833 349549 598704 144365 823870 788566 137449 61394 484783 520080 245029 669947 463486 849113 877860 147677 168936 399322 223703 835876 366948 267048 404793 546231 615606 549147 129867 131190 502599 267987 157345 713909 708716 829598 517836 102050 414867 921484 509343 410033 714137 413690 663872 69770 979333 516250 594554 832928 470439 67752 390911 448809 172024 868571 727102 412238 783053 42944 718790 294010 454564 366037 667873 14306 92871 494582 260627 602116 215675 651071 865606 299900 817696 246759 748710 426 607578 489005 447816 705702 21301 740620 751181 340916 623003 310507 908659 618254 594997 637130 526…
Output: 4369885

Example 3:

Input: 1433 97615 128623 418740 101249 29664 549855 407523 910216 163855 490019 54120 543361 723416 609874 910796 624231 49560 353364 86436 117457 827689 96693 119795 4798 727389 192323 495310 710930 562630 495236 284611 193042 781218 243670 844927 330632 499632 694642 260377 602978 267640 143154 62371 564463 43149 478104 880889 905360 415746 96189 957701 531246 47736 791595 397774 3712 48524 817183 1098 120992 440660 659414 760324 556036 561604 2813 470315 810195 506621 670579 503072 959821 162699 267376 517370 505576 309276 357986 366534 435306 69788 89926 528844 123020 136901 138353 885225 217644 19901 214002 719550 548796 218609 498421 150168 700828 506869 433659 715504 20608 103304 582846 779161 284411 498893 77383 88388 429445 476807 943691 615179 228818 187525 512309 578029 275079 275091 8…
Output: 4648

Constraints:

2 <= n <= 3516; 1 <= a[i],k <= 1000000.

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