QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#741359#8057. Best Carry Player 4quark404#AC ✓73ms12368kbC++202.1kb2024-11-13 14:10:462024-11-13 14:10:47

Judging History

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

  • [2024-11-13 14:10:47]
  • 评测
  • 测评结果:AC
  • 用时:73ms
  • 内存:12368kb
  • [2024-11-13 14:10:46]
  • 提交

answer

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

#define int long long
#define rep(a, b, c) for (int a = b; a <= c; ++a)

int n;
int a[500005];
int b[500005];
void init()
{
    cin >> n;
    int ca = 0, cb = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        ca += a[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> b[i];
        cb += b[i];
    }
    if (ca > cb)
    {
        for (int i = 0; i < n; i++)
            swap(a[i], b[i]);
    }
    // pre 0 in a,ca<cb
    return;
}

bool hava[500005], havb[500005];
void solve()
{
    for (int i = 0; i <= n; i++)
        hava[i] = havb[i] = false;
    int cnt_n1 = 0;
    bool hav_mplus = false;
    int now = 0;
    for (int i = n - 1; i >= 0; i--)
    {
        now = max(now, (n - 1) - i);
        while (a[i] > 0 && now <= n - 1)
        {
            if (b[now] == 0)
            {
                now++;
                continue;
            }
            if (i + now >= n)
                hav_mplus = true;
            int v = min(a[i], b[now]);
            cnt_n1 += v;
            a[i] -= v;
            b[now] -= v;
            havb[now] = true;
        }
    }
    if(b[n-1]>0)
    {
        havb[n-1]=true;
        cnt_n1+=b[n-1];
        b[n-1]=0;
    }
//    assert(b[n - 1] == 0);
    if (hav_mplus == true)
    {
        cout << cnt_n1 << '\n';
        return;
    }
    int r = -1;
    for (int i = n - 1; i >= 0; i--)
    {
        if (b[i] > 0)
        {
            r = i;
            break;
        }
    }
    for (int i = r - 1; i >= 0; i--)
    {
        if (havb[i] == true)
        {
            cout << cnt_n1 << '\n';
            return;
        }
    }
    int hav_diff = 0;
    for (int i = 0; i <= n - 1; i++)
    {
        if (havb[i] == true)
            hav_diff++;
    }
    if (hav_diff >= 2)
        cout << cnt_n1 - 1 << '\n';
    else
        cout << 0 << '\n';
    return;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
    {
        init();
        solve();
    }
    return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

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

input:

5
2
1 2
3 4
3
1 0 1
0 1 0
4
1 0 0 1
1 1 1 1
5
123456 114514 1919810 233333 234567
20050815 998244353 0 0 0
10
5 3 5 3 2 4 2 4 1 5
9 9 8 2 4 4 3 5 3 0

output:

5
1
2
467900
29

result:

ok 5 number(s): "5 1 2 467900 29"

Test #2:

score: 0
Accepted
time: 45ms
memory: 5768kb

input:

100000
5
0 1 1 1 1
0 0 1 0 0
5
0 0 0 0 0
1 1 1 0 0
5
0 0 2 1 1
0 2 1 0 1
5
0 0 0 0 0
1 2 1 0 0
5
0 1 0 1 1
0 0 1 1 1
5
2 0 0 0 1
1 0 0 0 3
5
2 0 0 1 1
0 2 1 1 1
5
0 0 0 0 2
0 0 0 0 1
5
0 0 0 0 0
0 1 1 0 0
5
4 0 0 0 0
0 0 0 1 0
5
0 0 0 0 1
2 1 1 0 0
5
0 2 3 0 0
0 0 0 1 0
5
1 1 1 0 1
1 0 1 0 1
5
0 0 0...

output:

2
0
4
0
3
3
3
2
0
0
1
1
3
0
3
0
0
0
0
0
0
0
4
0
4
1
0
2
3
3
1
5
0
0
2
0
0
1
1
0
0
3
5
3
2
2
2
0
1
2
2
2
0
3
0
2
1
1
0
1
0
4
0
0
2
2
0
3
3
0
2
0
1
0
0
1
1
2
0
3
4
0
2
5
0
2
1
0
0
0
3
2
3
0
2
0
4
3
3
0
2
2
0
1
3
1
1
0
0
0
1
0
3
2
2
0
2
1
1
0
1
0
0
2
4
1
3
3
2
2
2
0
2
0
0
2
3
1
3
1
0
2
2
3
0
1
2
0
1
1
...

result:

ok 100000 numbers

Test #3:

score: 0
Accepted
time: 28ms
memory: 5684kb

input:

1000
500
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

0
1
1
2
2
2
0
0
0
3
1
1
2
0
1
0
1
1
3
0
0
4
3
1
4
4
0
0
2
1
3
3
0
0
1
0
1
1
0
0
2
1
2
0
3
1
3
1
3
4
2
1
1
2
3
0
0
1
2
0
0
1
1
1
1
2
1
2
2
0
2
2
1
1
3
0
0
1
2
0
1
3
0
0
1
1
0
0
1
0
3
1
2
0
0
5
1
1
1
3
1
4
1
0
0
0
0
0
1
3
1
2
1
0
0
0
0
0
1
1
0
4
0
1
1
3
0
1
0
0
2
3
0
1
2
1
1
1
0
3
0
0
3
2
1
1
0
1
0
1
...

result:

ok 1000 numbers

Test #4:

score: 0
Accepted
time: 73ms
memory: 5704kb

input:

100000
5
119777838 337555280 806504015 458289944 321614229
979242871 431783189 423329635 193632121 7339369
5
189264782 667669243 753322761 861814678 224007583
977519325 104432095 940220826 712094722 903574615
5
977791540 278658984 601762324 633391706 36807634
689562032 997406456 118939957 891425821 ...

output:

1377698543
2884329841
1699584169
2132012702
2531472710
2754014935
2585135038
2577893498
2034726862
2303377730
1476887044
2618960687
1626312268
1068946376
600795101
927483202
2151016849
2256729729
2291627593
1751199962
2412405837
1884010446
2553701265
2014856631
848686688
1069641213
2412585811
167144...

result:

ok 100000 numbers

Test #5:

score: 0
Accepted
time: 61ms
memory: 5640kb

input:

50000
10
18209490 798013131 762297136 184230300 323229686 771738936 850827138 201740028 818693101 945688434
101715068 966337103 309026840 698679951 666034197 810411289 841033024 740762082 484989962 19640395
10
608177485 700383507 317699894 982085408 908794603 92931066 880099629 965892642 576147264 9...

output:

5341540062
3811346608
3280168940
4222050470
4327730826
4389011469
5146997799
3799138189
4028437054
3650616128
4267213780
5220650313
3272450503
3560399774
5130261345
4384881302
4681302604
5415587476
2376088103
3344427945
3701410392
3434767065
4969556102
4474318648
4751503347
3701971157
5053000969
397...

result:

ok 50000 numbers

Test #6:

score: 0
Accepted
time: 62ms
memory: 7680kb

input:

5000
100
405163017 116989072 685766112 551211950 862199350 861827829 564364529 922314891 241721254 160976656 891732149 553649064 445152950 859742462 235262967 648909226 943054063 484936253 414150625 995061073 662853643 367723189 348457562 591856009 309322986 450413840 159926452 24214846 79239852 397...

output:

44348367445
47318596151
43893435579
49579921753
48669603728
45875221434
49002488594
53587378598
52208712766
49588253701
50196256163
49596309746
48141429048
49878478140
49036091100
46395088830
42672527744
41761915575
47439675311
47743457344
44672635972
50006245688
49397345810
46906644735
49589049416
...

result:

ok 5000 numbers

Test #7:

score: 0
Accepted
time: 60ms
memory: 7724kb

input:

500
1000
193550719 323493453 457420643 784509248 590688212 53858799 864840302 864699978 833248388 388148011 424847622 153776183 812936693 826657538 546327769 8986082 692715231 409800344 238099504 373879563 776749117 721714043 87525288 267321580 716697878 959194006 945266703 700945389 403532515 62661...

output:

465088900904
505514759606
489135202623
496905462876
484245812646
489774003871
497113250036
495356965473
487989876653
478735387405
492452909500
477359116614
476644416427
496024593454
511879486093
489977997571
487118685797
482393118166
500657058671
495034745130
463481958257
494092548341
498541253420
4...

result:

ok 500 numbers

Test #8:

score: 0
Accepted
time: 60ms
memory: 5776kb

input:

50
10000
553995858 246962428 824402293 323478911 680777105 103832678 585415164 992760839 343503903 178165091 12159583 994935001 342595423 59449818 679792998 816039830 731856694 560299370 549956669 133588429 444088799 47439002 33732378 667849963 779213360 312649757 413654325 204037978 407607851 37016...

output:

4934445638422
5004001488974
4977801387386
4989770542861
4943635086274
4943321860665
4991292690262
4973954855238
4988511939705
5018237958210
4977930376515
4933073917545
4971084263806
4946670696385
4936093052793
5021060989890
4950350493770
4983314449815
4983863160783
5008348159840
4971191273387
495994...

result:

ok 50 numbers

Test #9:

score: 0
Accepted
time: 61ms
memory: 7780kb

input:

5
100000
55467530 650020741 57699590 51967772 504211856 67871962 527800251 879255265 275707965 711280566 612286703 26282254 309510499 1918401 39869854 860668290 361753493 794313666 928775160 911047415 93046944 491539438 414230658 370192146 951557038 97990007 385352159 233363349 16821851 997867917 52...

output:

49811853885925
49898102768915
49899712412574
50041437439141
49960859308453

result:

ok 5 number(s): "49811853885925 49898102768915 ...4 50041437439141 49960859308453"

Test #10:

score: 0
Accepted
time: 61ms
memory: 12368kb

input:

1
500000
889704374 950018223 920744105 136539883 13949458 99367986 130730288 42613586 166125956 657352532 642534716 229782745 195803762 756158990 891814184 512424712 766825853 128026842 999178366 359139037 835443410 889093206 305756461 487796242 162360521 260591109 47531278 627471500 56697038 350637...

output:

249921514093790

result:

ok 1 number(s): "249921514093790"

Test #11:

score: 0
Accepted
time: 73ms
memory: 7816kb

input:

100000
5
359491925 881344562 806504015 458289944 321614229
836444760 898390145 872363318 337555280 119777838
5
777374842 892008150 224007583 977519325 104432095
763700787 995718524 712061483 861814678 753322761
5
999707722 999162621 903792638 337158035 413950550
839808029 148963521 891425821 1189399...

output:

2043741306
2921096442
2570686305
2896367549
2651492085
3210988499
1898391621
2514599521
3322162113
2531455742
2382435060
1623537742
2761755396
2313798602
2910673710
2645618786
3079296518
2334186747
2976862915
2555551117
3633017866
3006717966
1374805257
2147522249
2482448884
1525821224
2241964715
212...

result:

ok 100000 numbers

Test #12:

score: 0
Accepted
time: 62ms
memory: 5616kb

input:

50000
10
588771083 830372258 914275824 504215670 323229686 771738936 850827138 201740028 818693101 945688434
963173630 819712828 335853956 992369499 838549713 866623127 184230300 762297136 798013131 18209490
10
423231151 985650606 995658982 120296832 989014338 976993991 668589240 98009563 430712533 ...

output:

5674667380
5657281045
4928513705
5977471185
3907009149
6659250721
5126670743
4930580785
4782271609
4690384571
3677857946
4015469917
5311177705
3472477494
6206628913
5035417885
4676717977
5125105597
5898977026
6197740677
6676390690
4643550502
4921838102
5296007891
6426161387
6116847418
5315586328
771...

result:

ok 50000 numbers

Test #13:

score: 0
Accepted
time: 62ms
memory: 7792kb

input:

5000
100
852142390 160717616 863714894 804290446 959866507 944721939 574476841 933412901 293953811 230779809 945001912 863843207 728632824 878822745 746101120 940088212 956567040 484936253 414150625 995061073 662853643 367723189 348457562 591856009 309322986 450413840 159926452 24214846 79239852 397...

output:

47842743501
55358809098
54472343533
50566292711
49623189866
51663113289
54014341709
55018333038
53846655561
52344005576
55193111410
51074714034
49999009285
54561786057
48509354795
49745928979
50874469629
47962027254
52456949162
51464778908
49405446314
54499938678
55271666356
49867512442
53403152314
...

result:

ok 5000 numbers

Test #14:

score: 0
Accepted
time: 57ms
memory: 7792kb

input:

500
1000
986566407 982877654 941971759 847036165 950496201 178242042 960309999 904124029 959326236 948642913 684416574 386029019 865467484 992252589 983317652 684089967 924812450 702912131 542415074 452394327 844473941 899783695 780525103 539319364 825770300 996509738 949331205 741458024 640929837 7...

output:

506324840960
506095212971
497399941586
498139479795
502412626406
499416702474
499436185812
496636941787
507081593810
487661962977
502339758110
479674901502
504021751784
513029327851
523131369964
508899980650
500490562928
494452783386
495563995977
498358354113
468001067956
504385422795
500026934295
4...

result:

ok 500 numbers

Test #15:

score: 0
Accepted
time: 61ms
memory: 7724kb

input:

50
10000
740546040 521721598 845223802 455954622 753174189 943568536 790403414 999490100 404538625 963808239 301544035 999755141 404400752 752531555 689175073 898755746 856945872 594075892 899986991 218570096 709725541 720730600 986199435 997949262 865745587 849516422 587333619 710274778 586021815 6...

output:

4993538196798
5049228437069
4983180415344
5002489260695
4988613946783
4980855325275
5013326999224
5008840367241
5014399872999
5043610099244
5022240117620
5000656159550
5013012411960
4979064810771
4948586688560
5025966922968
4983892893497
5002712757827
4995474855276
5010916640229
4988717372127
497397...

result:

ok 50 numbers

Test #16:

score: 0
Accepted
time: 53ms
memory: 7920kb

input:

5
100000
417182124 754831238 240231214 740860695 860815315 652497581 679743570 960890491 527159584 840971504 671132100 981767531 888089841 190319534 846418326 870816056 854136428 880011801 939195768 957025247 843707548 744990874 814390403 750011917 959704964 907781984 397768613 420060826 921808536 9...

output:

49986743502714
50069130499387
50003544218856
50076418978648
50184078732360

result:

ok 5 number(s): "49986743502714 50069130499387 ...6 50076418978648 50184078732360"

Test #17:

score: 0
Accepted
time: 44ms
memory: 7724kb

input:

500
1000
323493453 457420643 784509248 590688212 53858799 864840302 864699978 833248388 388148011 424847622 153776183 812936693 826657538 546327769 8986082 692715231 409800344 238099504 373879563 776749117 721714043 87525288 267321580 716697878 959194006 945266703 700945389 403532515 6266191 3808450...

output:

0
1504687002
522075127
1684329928
0
0
0
0
0
623029068
842979857
0
0
807916054
0
0
0
0
431718241
0
0
0
0
0
0
0
0
0
235258529
0
0
0
1233105924
0
0
1713799764
998008861
0
633303181
0
259000654
0
0
0
0
0
0
0
0
0
0
0
0
0
0
775300987
0
0
695350510
617581070
0
0
1206588944
0
0
938486905
0
980849176
7248517...

result:

ok 500 numbers

Test #18:

score: 0
Accepted
time: 44ms
memory: 5728kb

input:

50
10000
246962428 824402293 323478911 680777105 103832678 585415164 992760839 343503903 178165091 12159583 994935001 342595423 59449818 679792998 816039830 731856694 560299370 549956669 133588429 444088799 47439002 33732378 667849963 779213360 312649757 413654325 204037978 407607851 370160413 61384...

output:

356817915
0
0
0
0
0
1991963105
1027213477
0
417975837
0
0
0
1132882207
0
0
0
0
346356370
2218889703
0
0
1126948988
0
0
0
773889246
972400238
0
0
805738175
0
602397336
368635266
0
1003615814
1724340391
329551376
661815506
1735278741
880509475
568432529
0
0
0
0
0
0
935745185
1083976002

result:

ok 50 numbers

Test #19:

score: 0
Accepted
time: 40ms
memory: 8520kb

input:

5
100000
650020741 57699590 51967772 504211856 67871962 527800251 879255265 275707965 711280566 612286703 26282254 309510499 1918401 39869854 860668290 361753493 794313666 928775160 911047415 93046944 491539438 414230658 370192146 951557038 97990007 385352159 233363349 16821851 997867917 521557696 4...

output:

0
0
0
755765166
0

result:

ok 5 number(s): "0 0 0 755765166 0"

Extra Test:

score: 0
Extra Test Passed