CT40763

The Frugal Pairs of Gusthaven

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the windmill fields of Gusthaven opens only for a perfect tally of stretches. Ysolde means to find out. 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 <= 3932; -1000000 <= a[i],k <= 1000000000.

Example 1:

Input: 2125 27631059 626707795 939975521 495310768 468664871 313041016 769628513 419092987 993225499 633294464 919657880 7462961 302282502 683814196 704649555 21566901 193456617 684631893 982925165 406309925 758510543 -184336 880048869 301164931 573518693 944127270 50949291 270662451 245007010 39138560 784872652 968487189 206229533 755210753 615307521 302360610 160528398 196051965 317463087 920808152 751614929 896307249 16434399 89791866 25548710 150693140 35607273 -271641 989301034 917495159 616854121 715616016 593220648 899687915 -743223 540130621 500655082 548789331 570708549 271972810 826440697 55686249 464098405 338306632 107879842 238484762 349416596 197204259 844362298 728753062 911968851 558061610 957741130 376573270 285290778 510659829 456849120 243123999 51622698 305917435 387739497 101…
Output: 1081

Example 2:

Input: 1481 1516419464 808751161 752203357 63730033 625919096 158624010 34296046 37217113 40613703 425801623 713501127 50749145 302470323 546621430 983181335 42611555 456061065 286188190 76578301 686100300 540283164 813765369 249299188 772084616 373763467 288920784 232924057 414658232 828630312 870623048 721652546 541439369 885432903 189780340 400189522 814791465 166262614 581846522 68232175 652310141 696843340 819899013 432598814 655162851 243430859 694652480 430027991 615012524 634451190 958384945 815698359 54662255 183468670 376015651 507948032 808755192 842066796 665154452 871582439 766001505 254577804 183346614 7112422 245219065 544344879 789465961 620760128 607223963 489228408 890469254 536549790 62095258 159532223 47940216 516892704 456224933 945587600 542966258 775418591 12371064 87177723…
Output: 952509

Example 3:

Input: 3806 1538296868 913985928 282762607 94960529 460554394 389840238 650816856 639000789 367565355 399744390 292916052 473753848 888101164 232853323 133005988 240506597 72243568 177453577 687368502 645899830 40644731 114107925 883171373 672775169 464257692 881809340 733788348 215828561 597219803 776328009 836607289 503928880 122543309 329777053 432926928 830905727 639834224 854774778 75130908 198481739 73649874 797970630 138877373 796493975 174478467 823828415 371277937 799053753 638980308 902872805 68823981 602820565 485717632 22546645 210859593 561019191 479081258 926098387 478568078 281203498 110419736 927338890 290248397 36336502 643660454 218058080 617631457 657221032 267294956 614130066 215990862 434492390 511046183 922973735 278516587 366725666 990073986 369034404 997484440 945404389 37…
Output: 6450174

Constraints:

2 <= n <= 3932; -1000000 <= a[i],k <= 1000000000.

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