QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#544469	#1654. Neo-Robin Hood	gao_yc	AC ✓	158ms	6816kb	C++20	1.1kb	2024-09-02 17:03:46	2024-09-02 17:03:47

Judging History

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

[2024-09-02 17:03:47]
评测

测评结果：AC
用时：158ms
内存：6816kb

查看

[2024-09-02 17:03:46]
提交

answer

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int N=1e5+10;
int n,a[N],b[N],p[N];
ll sa[N],sb[N];
priority_queue<int> q;
bool check(int k){
    rep(i,1,n) sa[i]=sb[i]=0;
    while(!q.empty()) q.pop();
    rep(i,1,k) q.push(-a[p[i]]),sa[k]+=a[p[i]];
    rep(i,k+1,n-k){
        sa[i]=sa[i-1];
        if(a[p[i]]>-q.top()) sa[i]+=q.top()+a[p[i]],q.pop(),q.push(-a[p[i]]);
    }
    while(!q.empty()) q.pop();
    rep(i,n-k+1,n) q.push(b[p[i]]),sb[n-k+1]+=b[p[i]];
    per(i,n-k,k+1){
        sb[i]=sb[i+1];
        if(b[p[i]]<q.top()) sb[i]+=b[p[i]]-q.top(),q.pop(),q.push(b[p[i]]);
    }
    rep(i,k,n-k) if(sa[i]>=sb[i+1]) return 1;
    return 0;
}
int main(){
    scanf("%d",&n);rep(i,1,n) scanf("%d",a+i);rep(i,1,n) scanf("%d",b+i);
    iota(p+1,p+n+1,1);sort(p+1,p+n+1,[&](int A,int B){return a[A]+b[A]>a[B]+b[B];});
    int l=1,r=n>>1,ans=0;while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)) ans=mid,l=mid+1;
        else r=mid-1;
    }printf("%d\n",ans);
    return 0;
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 5868kb

input:

5
2 3 4 5 6
1 2 3 4 5

output:

result:

ok single line: '2'

Test #2:

score: 0

Accepted

time: 0ms

memory: 3936kb

input:

4
1 2 4 2
5 6 9 7

output:

result:

ok single line: '0'

Test #3:

score: 0

Accepted

time: 0ms

memory: 3932kb

input:

4
9 19 6 5
20 3 16 19

output:

result:

ok single line: '1'

Test #4:

score: 0

Accepted

time: 0ms

memory: 3872kb

input:

8
4 4 9 10 3 12 8 3
17 17 15 10 17 14 2 13

output:

result:

ok single line: '3'

Test #5:

score: 0

Accepted

time: 0ms

memory: 3916kb

input:

8
11 2 1 1 1 7 6 12
20 15 12 16 13 8 7 16

output:

result:

ok single line: '2'

Test #6:

score: 0

Accepted

time: 0ms

memory: 3916kb

input:

8
1 6 7 18 1 15 16 2
15 1 6 20 10 10 12 8

output:

result:

ok single line: '4'

Test #7:

score: 0

Accepted

time: 1ms

memory: 5956kb

input:

8
11 10 12 8 3 20 16 19
17 14 17 14 17 8 2 14

output:

result:

ok single line: '4'

Test #8:

score: 0

Accepted

time: 0ms

memory: 3924kb

input:

8
8 19 13 20 9 4 12 7
11 13 5 6 1 9 11 14

output:

result:

ok single line: '4'

Test #9:

score: 0

Accepted

time: 0ms

memory: 3932kb

input:

8
11 2 4 9 13 5 4 16
10 18 19 20 15 10 14 15

output:

result:

ok single line: '3'

Test #10:

score: 0

Accepted

time: 1ms

memory: 5968kb

input:

8
7 2 4 9 9 3 19 8
7 12 8 2 13 11 20 18

output:

result:

ok single line: '4'

Test #11:

score: 0

Accepted

time: 0ms

memory: 3972kb

input:

8
18 14 18 9 17 13 2 3
9 16 7 20 10 12 10 4

output:

result:

ok single line: '4'

Test #12:

score: 0

Accepted

time: 1ms

memory: 5868kb

input:

8
15 5 12 3 7 14 8 19
5 18 10 19 6 2 9 13

output:

result:

ok single line: '4'

Test #13:

score: 0

Accepted

time: 1ms

memory: 5976kb

input:

8
2 13 15 9 5 2 5 13
13 8 20 14 15 20 14 6

output:

result:

ok single line: '3'

Test #14:

score: 0

Accepted

time: 0ms

memory: 3860kb

input:

8
5 3 1 2 1 1 9 3
17 3 6 8 8 8 5 14

output:

result:

ok single line: '3'

Test #15:

score: 0

Accepted

time: 0ms

memory: 3924kb

input:

1
3
18

output:

result:

ok single line: '0'

Test #16:

score: 0

Accepted

time: 0ms

memory: 3848kb

input:

2
19 15
7 17

output:

result:

ok single line: '1'

Test #17:

score: 0

Accepted

time: 1ms

memory: 6012kb

input:

3
5 20 3
18 15 15

output:

result:

ok single line: '1'

Test #18:

score: 0

Accepted

time: 0ms

memory: 5944kb

input:

4
1 8 10 5
20 14 20 14

output:

result:

ok single line: '0'

Test #19:

score: 0

Accepted

time: 0ms

memory: 6008kb

input:

5
5 20 18 6 14
14 4 17 1 18

output:

result:

ok single line: '2'

Test #20:

score: 0

Accepted

time: 1ms

memory: 5956kb

input:

6
3 12 3 7 11 13
14 4 10 16 15 20

output:

result:

ok single line: '3'

Test #21:

score: 0

Accepted

time: 1ms

memory: 5904kb

input:

6
6 2 1 5 1 7
9 10 13 20 19 14

output:

result:

ok single line: '0'

Test #22:

score: 0

Accepted

time: 0ms

memory: 3920kb

input:

6
13 20 7 5 1 6
7 3 20 19 11 18

output:

result:

ok single line: '2'

Test #23:

score: 0

Accepted

time: 0ms

memory: 3852kb

input:

6
8 5 8 8 1 14
17 11 11 15 11 4

output:

result:

ok single line: '2'

Test #24:

score: 0

Accepted

time: 0ms

memory: 3936kb

input:

6
1 3 7 10 17 3
20 8 13 18 15 9

output:

result:

ok single line: '2'

Test #25:

score: 0

Accepted

time: 1ms

memory: 5868kb

input:

6
17 13 3 9 14 12
12 1 3 1 5 3

output:

result:

ok single line: '3'

Test #26:

score: 0

Accepted

time: 0ms

memory: 3932kb

input:

16
90 17 16 28 24 72 15 86 77 49 6 32 5 34 59 31
13 73 61 74 99 22 86 48 28 42 98 28 86 63 50 47

output:

result:

ok single line: '7'

Test #27:

score: 0

Accepted

time: 1ms

memory: 5972kb

input:

16
26 13 30 66 25 40 38 49 26 50 26 16 37 32 20 50
94 89 72 56 100 72 31 23 60 65 87 86 56 35 84 35

output:

result:

ok single line: '5'

Test #28:

score: 0

Accepted

time: 0ms

memory: 3968kb

input:

16
88 52 6 58 24 76 30 58 37 79 58 10 84 13 28 65
12 44 91 16 44 17 37 26 39 45 35 89 13 86 58 12

output:

result:

ok single line: '8'

Test #29:

score: 0

Accepted

time: 0ms

memory: 3872kb

input:

16
68 34 37 61 29 11 16 8 64 97 35 14 52 15 6 83
58 90 32 32 39 59 98 47 40 94 87 87 90 91 33 89

output:

result:

ok single line: '8'

Test #30:

score: 0

Accepted

time: 1ms

memory: 6008kb

input:

16
12 41 20 44 24 66 95 98 87 94 21 10 20 5 87 50
70 83 80 57 58 35 30 47 40 21 100 97 93 80 16 23

output:

result:

ok single line: '8'

Test #31:

score: 0

Accepted

time: 0ms

memory: 3936kb

input:

16
59 6 92 1 41 13 10 12 33 10 64 81 3 22 34 6
19 87 46 95 45 64 69 93 64 89 87 9 88 57 79 93

output:

result:

ok single line: '5'

Test #32:

score: 0

Accepted

time: 80ms

memory: 6708kb

input:

100000
2053 229 2895 284 1592 136 621 1640 618 152 3133 354 852 2704 1284 982 575 2985 1500 1375 872 1380 1944 3001 654 351 2753 797 52 931 2369 618 547 714 2200 28 587 1043 77 952 1542 1235 994 5422 1080 961 1598 1605 1277 121 4053 1459 187 99 1199 476 270 1332 792 1828 1918 1535 3650 3028 1632 628...

output:

result:

ok single line: '2029'

Test #33:

score: 0

Accepted

time: 34ms

memory: 6632kb

input:

100000
853 2133 507 1954 874 4069 1531 389 74 3546 1008 419 520 337 5155 837 402 742 134 2381 3000 663 1384 430 260 22 2106 1038 2276 609 1205 206 1761 2421 1016 1337 923 769 2100 2877 7 3543 94 1969 3395 938 1062 4133 313 4005 1187 3151 1388 1653 3310 697 1762 1062 168 1242 647 394 864 2402 525 119...

output:

result:

ok single line: '2141'

Test #34:

score: 0

Accepted

time: 105ms

memory: 6760kb

input:

100000
3490 2074 5007 479 5458 295 4921 4065 1411 125 6586 3126 3843 1147 5156 5585 2064 4518 2828 3422 8876 1024 2132 1605 23 2409 2585 190 51 6877 3067 4114 4284 2836 1950 5736 1850 5454 866 2016 1013 113 1558 950 4031 2751 90 628 4200 2241 2783 3670 2940 1444 430 409 1340 3520 1446 170 4455 3141 ...

output:

result:

ok single line: '14815'

Test #35:

score: 0

Accepted

time: 42ms

memory: 6708kb

input:

100000
599 201 153 1737 2348 571 919 1481 90 741 23 811 870 4317 370 89 934 922 2467 2230 413 632 2048 1024 540 2402 1491 809 516 410 524 1686 80 1501 249 166 1690 1550 2110 1153 2144 171 1409 278 2295 480 2018 1027 2792 590 2713 1055 916 301 434 714 885 3067 650 31 685 2248 851 702 2777 834 1058 14...

output:

result:

ok single line: '520'

Test #36:

score: 0

Accepted

time: 67ms

memory: 6772kb

input:

100000
604 1170 2153 159 1794 3426 602 744 170 5228 548 1083 3574 5637 3910 3724 270 600 3515 389 1757 1070 1023 94 2436 3083 4531 150 422 574 366 660 1856 636 463 148 673 1138 628 3539 766 986 247 232 1394 4654 139 3833 477 549 561 207 172 905 3365 638 2520 990 2703 4636 349 2733 5158 67 1098 1030 ...

output:

result:

ok single line: '3926'

Test #37:

score: 0

Accepted

time: 158ms

memory: 6636kb

input:

100000
221787385 187960463 89864847 200553069 58578048 372350040 351462930 410830366 210428044 64463189 177377303 256955780 294843362 53864442 236386120 411548592 215471659 608121286 5689384 426981624 739508568 188280153 115938512 620326342 213758405 489928398 615762853 902458594 576800416 398033701...

output:

result:

ok single line: '28236'

Test #38:

score: 0

Accepted

time: 148ms

memory: 6776kb

input:

100000
890483701 291497283 265584734 413903803 66910453 83693502 415913668 39793489 704999044 236841381 487767571 717243046 337555435 24855373 267079704 800292484 177160848 92046446 354235121 241598277 208201641 140409485 327141391 162646525 885761981 232376692 644238922 333844395 47188684 33562887 ...

output:

result:

ok single line: '28387'

Test #39:

score: 0

Accepted

time: 117ms

memory: 6676kb

input:

100000
382098089 50606676 24387075 9022689 82995668 87071422 40584654 41476952 3356896 64965999 263141493 41220587 92692109 175282400 240988130 10147218 394563108 3657098 102963360 140137544 248974873 31137962 19744553 657509721 224772978 363798807 16570024 31189001 41371947 86875479 121240587 38236...

output:

result:

ok single line: '2064'

Test #40:

score: 0

Accepted

time: 104ms

memory: 6760kb

input:

100000
20532790 169988062 16790452 96310238 47082978 150609756 136857442 199208580 88100435 180697689 137805461 77254186 13037907 90130966 101735675 464492441 277009920 7369174 13441594 98665314 9505429 9299771 20943480 7426825 39632163 8514473 22191366 10287899 72170316 191028877 133140413 67627776...

output:

result:

ok single line: '529'

Test #41:

score: 0

Accepted

time: 148ms

memory: 6812kb

input:

100000
397576211 483467659 762463529 530337707 371100999 62444136 385085296 307208756 55386368 120048670 17472772 217297767 159259429 597400390 409500976 494483611 400741436 412247549 84626859 532164820 11948777 294506477 310959680 781350055 342419257 117519753 660136241 695764407 545519551 66050607...

output:

result:

ok single line: '28364'

Test #42:

score: 0

Accepted

time: 143ms

memory: 6772kb

input:

100000
382564703 850901387 36411303 461995522 170677289 66339636 432553925 86944135 879485333 492116479 179690425 670468730 23007134 235821129 137703984 342869067 33283372 353882222 502146470 356308757 807568794 141782380 622924774 171226407 66058074 161446054 57305981 144817217 306270549 228016709 ...

output:

result:

ok single line: '28380'

Test #43:

score: 0

Accepted

time: 117ms

memory: 6780kb

input:

100000
163778857 85362520 166130923 136568592 64202370 100754279 62280701 140380186 73750166 35578237 180994140 131252543 97873904 25027884 181043483 389577498 72000124 34816892 37166951 526337869 1223013 33314505 91798948 55076200 75237310 182344467 60947732 384203563 32194422 232139753 13027106 46...

output:

result:

ok single line: '1019'

Test #44:

score: 0

Accepted

time: 144ms

memory: 6816kb

input:

100000
190584158 19093702 117283780 758509169 567775449 883920606 319680094 370544561 750412047 944897742 929606570 997103474 498449547 356744673 99440207 15831091 208766918 115537105 36593470 181273386 344473184 846939188 637691440 597645438 11610158 769273377 870265046 64192025 12270064 410487693 ...

output:

result:

ok single line: '50000'

Test #45:

score: 0

Accepted

time: 115ms

memory: 6752kb

input:

100000
143646595 105715734 194631074 57027707 90699624 358441542 123214471 26551050 61431178 147876703 31188963 180210304 220322892 113315231 109176145 199584640 213012546 196962870 331883883 22915263 15949255 174772307 104438431 114618133 9561696 103861006 251287914 311618631 186134120 33082088 835...

output:

result:

ok single line: '1020'

Test #46:

score: 0

Accepted

time: 128ms

memory: 6752kb

input:

100000
95323711 461969782 111651638 387900489 9553104 168259501 184434988 235714309 3914392 85188278 31666775 150598418 149058389 118241887 50383103 102887109 225721258 123475219 189959053 133729124 73094139 57827433 340426535 200792692 153248142 154363100 101645667 116892564 92682446 245802949 2142...

output:

result:

ok single line: '3785'

Test #47:

score: 0

Accepted

time: 125ms

memory: 6756kb

input:

100000
302246001 115367635 149796528 328160958 290882566 147675842 12912768 41640170 342018992 199877475 30201368 647515549 297487402 10790415 110091265 21611126 35447930 117979163 435725996 249242177 35127968 180776511 541867044 119605951 14023852 37255039 151886164 56013381 100425008 130468760 174...

output:

result:

ok single line: '3954'

Test #48:

score: 0

Accepted

time: 125ms

memory: 6816kb

input:

100000
78508510 299505838 58792128 99541631 283774927 464671619 34870405 112976301 118856498 36230088 63433312 579111022 110647924 116493798 103071163 28147232 142584532 330806770 115736179 35493043 216281181 343912338 279083790 203851719 95673400 461941835 614471846 259569764 166164703 646636601 66...

output:

result:

ok single line: '7669'

Test #49:

score: 0

Accepted

time: 125ms

memory: 6772kb

input:

100000
26629384 265031479 57885133 113261096 47512018 331829186 252186350 345934326 37907368 6362403 17221016 58995114 112516855 29271720 101682520 194861047 37134412 128730599 550330745 182817941 28346489 8873493 194964958 29357402 291385000 194080054 71304982 256219575 155416833 608214 147133710 2...

output:

result:

ok single line: '1965'

Test #50:

score: 0

Accepted

time: 104ms

memory: 6752kb

input:

100000
56357535 33398744 109150928 60390204 16760247 149598551 72310541 67095064 35875826 16044455 175623079 88974699 27346299 450279 131875952 36223783 132319841 64716014 20904971 31617436 11071283 36258153 1062946 38048851 31348192 248775577 65403048 23982090 5277712 87419339 95039563 117408036 50...

output:

result:

ok single line: '523'

Test #51:

score: 0

Accepted

time: 139ms

memory: 6712kb

input:

100000
608299813 857653687 875507159 771648766 993099380 248551388 684615395 647129312 501518194 387763184 400350366 943711612 366500440 993894938 354535434 917717834 9941772 952969109 32327061 174767235 597307972 436504395 283101868 530087620 677993858 810176271 286272112 370489452 356067968 681677...

output:

result:

ok single line: '50000'

Test #52:

score: 0

Accepted

time: 34ms

memory: 6704kb

input:

100000
57815571 41647569 331555093 67673845 296696348 123191827 7854432 253283236 489864907 11470971 85662659 47260246 27967922 41232821 174210537 24508093 35854612 287472428 41956471 93565212 203232507 30344406 19528096 155143339 95942327 82499172 33116258 17182851 96869578 190066720 28950305 42855...

output:

result:

ok single line: '1021'

Test #53:

score: 0

Accepted

time: 118ms

memory: 6768kb

input:

100000
298825848 582967533 757982159 613512446 390368152 81650999 149292076 810794586 676528929 185523902 982338821 50848168 247441726 611204988 68658349 537731206 657606434 632370730 284518523 317832476 69032892 889411120 100061632 968399383 900167484 36947378 896379768 355696919 931592293 77110942...

output:

result:

ok single line: '50000'

Test #54:

score: 0

Accepted

time: 115ms

memory: 6804kb

input:

100000
287509526 10906215 468712294 817584632 66324911 111203696 154953331 771245717 25764458 73773979 315712022 251851596 209477491 263068579 227101376 190402308 712177956 425172566 76702192 367806621 806287299 127733538 720048115 116196911 796026679 327956690 81320311 489261097 672111343 129054231...

output:

result:

ok single line: '50000'

Test #55:

score: 0

Accepted

time: 56ms

memory: 6704kb

input:

100000
280655703 249577548 234274007 119280369 415998499 479986991 249502086 205589499 360161582 264340683 277726367 50895751 131309739 71991286 367224605 139911740 148219681 440193615 60357519 261063837 252967612 405371980 353175766 28098376 94418558 29650499 189014900 60052250 60573582 48259921 50...

output:

result:

ok single line: '15238'

Test #56:

score: 0

Accepted

time: 35ms

memory: 6812kb

input:

100000
32069207 85286374 136366472 96789307 3754108 43616264 417356016 62990268 4320747 131377671 249573887 243419778 53995420 54859008 79009211 188863293 12632221 206049532 64440171 255084782 139756005 66790502 50115377 104594454 31540277 17561693 173539501 118557192 47342076 98385226 85194001 4254...

output:

result:

ok single line: '3977'

Test #57:

score: 0

Accepted

time: 52ms

memory: 6672kb

input:

100000
280655703 249577548 234274007 119280369 415998499 479986991 249502086 205589499 360161582 264340683 277726367 50895751 131309739 71991286 367224605 139911740 148219681 440193615 60357519 261063837 252967612 405371980 353175766 28098376 94418558 29650499 189014900 60052250 60573582 48259921 50...

output:

result:

ok single line: '15238'