CT40073

Cartwright and the Frugal Pairs

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the frontier camp of Duskwood opens only for a perfect tally of segments. Cartwright 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 <= 3408; -1000000 <= a[i],k <= 1000000000.

Example 1:

Input: 306 1526236787 150629003 86789318 210715980 154597140 280049860 111539523 127425157 508738024 859976795 676103334 670587710 243895597 497204966 293582098 405468870 275734528 125403459 520090884 309353624 36725890 669140504 577506354 351609816 589182480 492570849 26130066 90745493 42690816 365163610 656614137 285708439 462300327 475125733 547307744 188301363 143692482 815955514 396705880 135021051 906499862 581496995 765016949 906371579 962780484 986988200 949587121 198268663 296218563 120276988 256962412 702587881 536985257 87228808 109668554 806208570 445380056 777692337 6461155 565729228 236260736 947897842 218817887 369873987 278610047 231596077 771475616 145020134 328870494 940663572 812230998 309751254 53821105 375421706 804120996 486713021 161126826 223546060 540735290 687066623 9560…
Output: 41335

Example 2:

Input: 2922 859908035 420307210 934823062 91288228 765442948 778454787 991480085 343241551 536647122 341581896 132191781 646916389 556277227 434678828 313673043 420661150 220316882 605559509 111820168 469997355 259283252 734567211 605914824 53427941 821320214 3656434 799584360 47242421 547006929 614212195 274450006 24749488 448542524 623849753 181941292 860952361 609639809 9838615 670009585 13113169 387764728 437762623 690259636 910566719 135054898 734482996 585830067 54249414 870986260 443536042 230541106 235985974 183316392 506257307 163684831 191926126 905093145 663910558 425224515 401627978 245908231 982848440 526150069 893225476 301797125 121314360 155664548 536464052 19232244 645247690 535950474 597668303 303390968 56099075 482977597 846677614 904486408 321006237 273101369 754653717 3633338…
Output: 1520534

Example 3:

Input: 2934 509053004 612547650 226235196 517290089 638655416 49779826 972236053 36732943 173864125 92387548 601938318 165871140 758664150 364431334 652111727 826778763 936595907 112047661 671265172 376677234 922734906 987033386 460289521 947752014 501470117 19439351 804009076 217150978 506354829 866536890 497513803 368499898 844411681 604465086 898979596 589636816 365460692 303867799 675410459 992556893 934260941 343177435 134392904 358154457 200183597 988614314 978748192 521350687 687699064 592175431 762993619 21590494 686580984 617578677 47200384 933162067 555227966 782629904 158783303 36964558 573582223 65833415 940262398 541277588 818165199 810645214 235387821 783364402 777393938 313157153 513082111 700824628 506037337 553542448 4220882 425542789 874888772 608512799 893016219 654685691 64582…
Output: 568687

Constraints:

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

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