CT32981

The Frugal Pairs Beneath Amberfield

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Caravans arrive at the wheat plains of Amberfield with crates of ribbons, and Tracker the valuer must account for every last one. 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 <= 1068; 1 <= a[i],k <= 1000000.

Example 1:

Input: 760 320663 25990 541760 967600 342386 283739 448170 116584 286353 582811 547007 42002 883285 404308 980368 805637 134193 400757 604708 482499 784134 758777 178706 235116 506564 589918 541833 615699 395316 313678 986159 430876 539808 989501 17182 768757 750138 213698 80541 372753 360005 637210 786061 26852 864070 368415 336221 397579 559444 453920 176004 251966 508876 157070 22123 371381 79480 835880 535518 378637 622701 139938 220085 969545 422950 276885 980122 868782 900181 107819 72040 59114 130496 395977 249476 128101 267011 616078 411876 740538 221561 265907 594855 75324 74795 417465 416059 138399 617040 524078 628165 754629 378475 98990 436235 172309 554427 754250 861169 914215 647450 120837 862879 107732 63643 229578 349995 551693 730345 508186 646761 513036 557395 156512 944050 8224…
Output: 12877

Example 2:

Input: 604 503519 21768 885776 219056 628175 109381 37462 309746 231866 674981 738224 472378 431258 345361 970290 853056 461196 648548 630751 905944 878950 389411 52907 377066 368004 949679 943145 257210 520133 856737 881281 582543 758536 124141 405599 233949 507364 879035 780452 750284 103837 728723 652123 562617 627214 121631 83185 724268 201491 62358 691558 402708 90068 77324 178090 246509 998265 708279 90869 544734 761390 623937 943827 777206 931325 419700 321609 647484 799444 266730 20623 996725 650210 755012 129726 666412 66454 412068 439876 32920 355229 698975 645371 264036 779119 284802 995505 862604 98868 300342 421292 898316 55939 490170 907172 766575 491544 162640 272746 169304 1920 654412 664599 506233 841706 956344 820449 434840 233661 501347 555134 668328 257516 633179 393903 527431…
Output: 22329

Example 3:

Input: 38 1242378 759126 769871 992010 441220 611863 132333 228281 148968 441646 246599 398954 440893 461044 277887 346062 781884 89003 766114 970491 562129 533695 171729 981023 897746 444082 498856 218214 180374 772640 676695 283413 869793 175363 423127 356434 959250 909436 354365
Output: 501

Constraints:

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

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