QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#752808#9123. Kth Sumhaiender288TL 2126ms4672kbC++231.5kb2024-11-16 09:53:442024-11-16 09:53:44

Judging History

你现在查看的是最新测评结果

  • [2024-11-16 09:53:44]
  • 评测
  • 测评结果:TL
  • 用时:2126ms
  • 内存:4672kb
  • [2024-11-16 09:53:44]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define fileio(name) if (fopen(name".inp", "r")) freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout)

const int maxn = 50004;
int n, k, a[maxn], b[maxn], c[maxn];

int calc(int v) {
    int res = 0;
    for (int i = 1; i <= n; i++) {
        int add = 0;
        if (a[i] + b[n] + c[n] <= v) {
            add += n*n;
        } else {
            int l = 0;
            for (int j = n; j > 0; j--) {
                if (a[i] + b[j] + c[n] <= v) {
                    add += n*j;
                    break;
                } else {
                    while (l < n && a[i] + b[j] + c[l+1] <= v) l++;
                    add += l;
                }
            }
        }
        res += add;
        if (res + add*(n-i) < k) return 0;
        if (res >= k) return res;
    }
    return res;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    fileio("");
    // freopen("debug.txt", "w", stderr);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
    }
    sort(a+1, a+1+n);
    sort(b+1, b+1+n);
    sort(c+1, c+1+n);

    int l = 0, r = 3e9;
    while (l <= r) {
        int mid = l+(r-l)/2;
        if (calc(mid) >= k) {
            r = mid-1;
        } else {
            l = mid+1;
        }
    }
    cout << l;

    return 0 ^ 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3600kb

input:

2 4
1 2
3 4
5 6

output:

10

result:

ok "10"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3672kb

input:

10 40
11 9 13 12 15 11 11 2 11 17
3 1 10 2 12 18 9 11 11 15
14 9 4 14 16 9 20 2 1 18

output:

14

result:

ok "14"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3672kb

input:

1 1
1000000000
1000000000
1000000000

output:

3000000000

result:

ok "3000000000"

Test #4:

score: 0
Accepted
time: 20ms
memory: 3668kb

input:

314 12491830
429392519 92131736 9460149 448874040 5326166 804308891 571581523 580832602 110825817 11150177 47845585 886171410 888601860 633656718 879205016 333690452 739013504 118317331 8289119 502971381 486014573 167383690 96016893 556946780 634198668 389358242 984894049 735281439 58642904 22106451...

output:

1346801336

result:

ok "1346801336"

Test #5:

score: 0
Accepted
time: 1ms
memory: 3656kb

input:

34 34490
133495256 283197838 857697935 858259368 959152648 301897236 990604260 865643006 704101978 322295867 324109158 258113372 423370893 16000407 224364583 353708691 265955784 183826167 813127458 476308169 634865805 973017138 197716378 674895784 956141489 277068847 534893183 817797721 662940992 82...

output:

2149314674

result:

ok "2149314674"

Test #6:

score: 0
Accepted
time: 2ms
memory: 3616kb

input:

162 3892887
763969065 810700429 42372207 636240914 502913712 840954780 778223217 445420701 2410846 338474264 231776510 588586138 368205344 103376804 569524150 783792347 87865355 617931224 986562016 523273886 488749745 483683293 299415863 792844787 204455380 164779452 748455830 195281294 930802591 80...

output:

2182951602

result:

ok "2182951602"

Test #7:

score: 0
Accepted
time: 1ms
memory: 3672kb

input:

86 413467
763039094 633170311 595642701 709189753 825336413 674979614 902278662 98827324 300719716 354652661 803007374 960528102 608007086 822156983 251120206 213876002 319840344 52036279 86367645 865206894 637600977 362945669 769711568 205761081 157801980 52490057 298454964 572764868 125035261 4872...

output:

1675510101

result:

ok "1675510101"

Test #8:

score: 0
Accepted
time: 9ms
memory: 3608kb

input:

214 7057935
98545611 529269121 443880485 487171300 369097477 582633376 321301399 678605020 893995877 2234839 79270945 291000867 847808829 204500671 596279774 233894241 478186405 117545115 891205983 838543682 491484917 873611825 871411053 323710085 406115873 645233371 143421391 950248441 24300640 758...

output:

1763767750

result:

ok "1763767750"

Test #9:

score: 0
Accepted
time: 1028ms
memory: 3912kb

input:

9429 823330096
710308717 885443360 151359742 257927627 89698847 133943367 458101850 441715448 448225213 867533556 948805555 168922334 660173729 242187286 990107147 920584508 611308123 525304427 558566303 443722397 295118124 112161359 258379911 198998755 698515100 523982637 41263636 383698580 8552056...

output:

185843818

result:

ok "185843818"

Test #10:

score: 0
Accepted
time: 994ms
memory: 3908kb

input:

10149 691846236
340782526 117978658 704630235 330876466 338492620 967968202 245720807 95122072 746534082 178679244 520036419 909460517 605008179 624530975 335266714 940602747 138250403 254376775 953339225 417059185 149002064 622827516 360079396 316947758 946828992 411693242 959858992 761182154 75447...

output:

160042939

result:

ok "160042939"

Test #11:

score: 0
Accepted
time: 1091ms
memory: 4356kb

input:

26277 120170888
971256336 940448541 552868020 445294502 955882613 875621964 664743544 674899768 413439170 194857641 796299991 871337063 844809922 711907373 680426281 739282622 1629172 393514539 758177562 464024901 297853296 133493671 461778881 66300541 195142884 4436555 804825418 138665726 22332656 ...

output:

34606249

result:

ok "34606249"

Test #12:

score: 0
Accepted
time: 952ms
memory: 3904kb

input:

9701 693719733
675359072 836547350 106138512 518243340 204676385 709646799 83766281 959710172 711748039 842439820 367530854 906842537 84611664 725654842 656989629 169366277 823538745 459023375 857983192 805957909 151737236 12756046 932074585 184249545 148489484 597179869 354824553 516149300 92159803...

output:

163052076

result:

ok "163052076"

Test #13:

score: 0
Accepted
time: 2126ms
memory: 4672kb

input:

43125 267268577
10865589 364049940 290812785 296224887 822066378 248704341 207821727 539487867 10056907 153585508 980230915 278784499 955817187 813031240 2149196 189384516 350481024 893128432 31417749 779294698 300588468 818389495 328741361 597165840 765399596 484890474 199790980 598665582 115830706...

output:

27436842

result:

ok "27436842"

Test #14:

score: 0
Accepted
time: 2120ms
memory: 4348kb

input:

26549 840817422
9935618 186519822 139050570 369173726 70860150 451325395 995440684 192894490 603333068 169763905 551461778 609257266 195618929 826778709 347308764 619468172 582456013 958637268 836256088 826260414 449439700 329055650 799037066 420147551 13713488 77633787 118386334 976149156 383692305...

output:

63457689

result:

ok "63457689"

Test #15:

score: -100
Time Limit Exceeded

input:

42677 709333562
640409427 82618632 987288355 147155272 688250143 990382938 414463421 772672187 901641938 185942303 122692641 981199229 435420671 914155107 323872111 49551827 404365585 392742323 936061718 168193421 598290933 839721806 900736551 833063847 967060089 965344393 963352762 58665437 9879903...

output:


result: