CT31246

The Frugal Pairs of Gusthaven

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Before the gates of the windmill fields of Gusthaven close for winter, Nora must finish the panels ledger - one figure at a time. 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 <= 3725; 1 <= a[i],k <= 1000000.

Example 1:

Input: 146 1441700 43580 18475 688957 531884 904506 893436 585609 551011 512815 563752 773623 335895 399969 150916 242178 488388 336273 11235 838133 142531 681753 575458 785834 20258 735632 732455 205904 601102 691766 73385 77593 601970 413478 816792 924730 821215 701024 710181 469424 645165 849180 920195 39793 296595 693309 603588 288093 464875 361354 486280 523469 549686 924496 266147 824308 438210 237203 816132 48189 947519 617879 95730 346210 697856 307441 548827 385717 84482 107654 491046 50047 256228 138760 330425 904950 42900 728362 182259 40155 243670 93705 934979 538298 591391 654050 366272 555757 469813 982201 641846 261442 983427 285451 838801 966667 376080 284923 524924 342597 993331 663028 788511 395058 720597 982229 323143 572453 153102 286960 402803 147613 480372 993279 471468 8971…
Output: 9080

Example 2:

Input: 2715 1920716 15809 930683 645386 512340 556336 638004 240886 226967 830920 466789 564812 359073 222262 639550 313217 270407 589206 596979 897038 129250 567538 448295 327320 642238 578227 666921 549918 641259 357711 908511 121363 138537 990290 571555 650951 678071 644512 125867 880056 825325 998523 42616 53961 125194 514244 142505 107349 42550 237206 917381 735975 533749 237940 735599 24021 55640 459790 506917 261096 134480 636917 184757 132254 172018 473327 671040 63104 888260 446808 338627 574948 195555 502696 20371 692244 191353 39716 650763 748315 743101 862989 791594 318665 981255 745804 392089 553905 281266 88780 1928 836813 342548 866102 338256 55790 90139 426374 841378 71463 654997 978762 282483 706680 542911 47881 813927 483279 405785 300430 54483 282652 711519 720586 61329 861450 …
Output: 3670828

Example 3:

Input: 187 1432103 819877 188829 96993 12355 299392 306351 84558 351395 389918 101640 626881 374360 689494 217313 160173 941956 659106 39250 214126 796264 263517 381081 853134 60849 488229 221395 878220 649250 152286 952213 801686 597601 789596 850773 742451 880070 985495 844605 579982 966002 808888 681337 984039 991895 272580 303687 696834 118722 680417 300151 731752 216218 850082 804243 712071 751579 45260 635915 402305 765946 463899 265975 697753 615206 800823 734000 322261 867876 535543 964495 154762 901538 956189 241673 879514 132092 172672 369650 421975 520607 603809 709663 599724 818721 834644 46417 303842 60104 639915 416653 155089 920504 903981 873438 729521 476344 316251 814645 604652 293708 83580 386549 620669 193730 466608 214225 482048 66105 350922 229497 537559 765505 328796 137379 …
Output: 14596

Constraints:

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

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