QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#618149 | #1961. Postman | Cheek_support | WA | 43ms | 13496kb | C++20 | 4.3kb | 2024-10-06 19:11:44 | 2024-10-06 19:11:45 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define mk(x,y) make_pair(x,y)
using namespace std;
int read(){
char ch=getchar();int x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
return f*x;
}
int n,m;
const int N=300100;
ll a[N],b[N];
pair<ll ,int> c[N];
int x,y;
bool bo[N];
void work1(){
int L=m,R=n-m-1;
if(L==0){
if(x==1)printf("%lld\n",a[n]-a[1]);
else puts("-1");
return;
}
if(R==0){
if(x==n)printf("%lld\n",a[n]-a[1]);
else puts("-1");
return;
}
ll ans=(1ll<<60);
{
ll res=0;
int t=n-x-R;
if(t>0){
if(t==n-x-1)res=a[n]-a[x+1];
else{
for(int i=1;i<=n-x-2;i++)
c[i]=mk(b[i+x],i+x);
sort(c+1,c+n-x-1);
ll num=0;res=(1ll<<60);
for(int i=1;i<=t;i++)
num+=c[i].first*2,bo[c[i].second]=1;
res=min(res,num);
int i=t;
for(int j=n-1;j>=n-t;j--){
if(bo[j-1]){
bo[j-1]=0;
num+=b[j]-2*b[j-1];
}else{
for(;!bo[c[i].second];)i--;
bo[c[i].second]=0;
num+=b[j]-2*c[i].first;
}
res=min(res,num);
}
}
}
ans=min(ans,res+a[x]+a[n]-2*a[1]);
}
for(int i=1;i<=n;i++)a[i]=-a[i];
sort(a+1,a+n+1);
for(int i=1;i<n;i++)b[i]=a[i+1]-a[i];
x=n-x+1;
swap(L,R);
memset(bo,0,sizeof(bo));
{
ll res=0;
int t=n-x-R;
if(t>0){
if(t==n-x-1)res=a[n]-a[x+1];
else{
for(int i=1;i<=n-x-2;i++)
c[i]=mk(b[i+x],i+x);
sort(c+1,c+n-x-1);
ll num=0;res=(1ll<<60);
for(int i=1;i<=t;i++)
num+=c[i].first*2,bo[c[i].second]=1;
res=min(res,num);
int i=t;
for(int j=n-1;j>=n-t;j--){
if(bo[j-1]){
bo[j-1]=0;
num+=b[j]-2*b[j-1];
}else{
for(;!bo[c[i].second];)i--;
bo[c[i].second]=0;
num+=b[j]-2*c[i].first;
}
res=min(res,num);
}
}
}
ans=min(ans,res+a[x]+a[n]-2*a[1]);
}
printf("%lld\n",ans);
}
void work2(){
// for(;;);
int L=m,R=n-m;
if(y<x){
for(int i=1;i<=n;i++)a[i]=-a[i];
sort(a+1,a+n+1);
for(int i=1;i<n;i++)b[i]=a[i+1]-a[i];
x=n-x+1;y=n-y+1;
swap(L,R);
}
if(R==0){puts("-1");return;}
if(L==1){
if(x==1&&y==n){
ll minn=(1ll<<60);
for(int i=2;i<n-1;i++)
minn=min(minn,b[i]);
if(minn==(1ll<<60))puts("-1");
else printf("%lld\n",a[n]-a[1]+2*minn);
return;
}
if(x==1||y==n)printf("%lld\n",2*(a[n]-a[1])-(a[y]-a[x]));
else puts("-1");
return;
}
if(L==0){
if(x==1&&y==n)printf("%lld\n",a[n]-a[1]);
else puts("-1");
return;
}
if(R==1){
if(y-x==1)printf("%lld\n",2*(a[n]-a[1])-(a[y]-a[x]));
else puts("-1");
return;
}
int t=y-x-R;
ll res=0;
if(t>0){
ll num=0;
for(int i=1;i<y-x-1;i++)
c[i]=mk(b[x+i],x+i);
sort(c+1,c+y-x-1);
for(int i=1;i<=t;i++)
num+=2*c[i].first;
res=num;
}
printf("%lld\n",res+2*(a[n]-a[1])-(a[y]-a[x]));
}
int main(){
n=read();m=read();
int k=read();
for(int i=1;i<=n;i++)a[i]=read();
x=0,y=a[n];
a[n+1]=0;n++;
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
if(a[i]==x){x=i;break;}
for(int i=1;i<=n;i++)
if(a[i]==y){y=i;break;}
for(int i=1;i<n;i++)b[i]=a[i+1]-a[i];
if(k==1)work1();
else work2();
return 0;
}
/*
5 4 2
-20 -15 20 30 10
5 4 1
-20 -15 20 30 10
7 1 2
10 13 -30 24 50 -5 -21
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 7860kb
input:
100 0 1 751 558 131 292 317 886 785 847 224 668 649 358 725 250 953 65 176 733 461 84 114 977 628 673 798 863 373 827 51 630 518 347 527 876 366 241 452 670 813 314 846 342 357 460 985 581 841 843 282 907 327 656 411 944 421 99 441 388 568 763 167 351 793 916 517 109 999 390 272 639 513 534 304 253 ...
output:
999
result:
ok single line: '999'
Test #2:
score: 0
Accepted
time: 0ms
memory: 8116kb
input:
100 50 1 654 349 533 94 619 754 498 939 469 518 3 661 431 214 195 198 989 548 561 312 262 629 807 981 624 639 178 765 706 782 888 611 553 363 336 91 176 485 735 791 596 455 390 760 995 202 417 82 798 883 209 155 725 908 789 56 49 899 231 423 815 228 314 400 748 946 736 840 385 446 938 284 10 917 593...
output:
1397
result:
ok single line: '1397'
Test #3:
score: 0
Accepted
time: 0ms
memory: 8216kb
input:
100 99 1 266 337 80 671 358 778 217 288 219 48 863 19 137 987 602 415 155 398 753 956 210 317 94 303 997 192 123 442 666 959 685 71 34 588 615 214 327 881 582 51 646 630 291 354 749 108 984 308 813 182 384 699 114 692 611 296 590 432 103 240 341 465 969 370 771 914 250 656 742 708 174 323 939 493 17...
output:
1986
result:
ok single line: '1986'
Test #4:
score: 0
Accepted
time: 1ms
memory: 7792kb
input:
100 100 1 713 172 634 763 181 502 78 995 598 751 792 961 585 335 952 343 375 627 651 515 856 121 743 931 18 492 726 517 136 143 314 993 80 29 283 427 248 274 114 200 535 94 174 782 818 90 806 88 104 808 910 892 791 462 304 676 67 973 901 891 705 567 475 444 949 846 299 735 233 914 803 27 810 210 396...
output:
-1
result:
ok single line: '-1'
Test #5:
score: 0
Accepted
time: 1ms
memory: 7716kb
input:
100 0 1 -102 -827 -638 -660 -604 -258 -692 -237 -927 -371 -129 -908 -830 -229 -585 -364 -103 -58 -975 -153 -563 -17 -201 -443 -56 -560 -606 -45 -891 -331 -349 -420 -266 -219 -482 -716 -51 -723 -876 -211 -121 -63 -814 -239 -937 -541 -74 -69 -334 -42 -227 -479 -571 -137 -913 -885 -525 -475 -930 -405 -...
output:
-1
result:
ok single line: '-1'
Test #6:
score: 0
Accepted
time: 1ms
memory: 8212kb
input:
100 1 1 -747 -27 -215 -283 -833 -584 -531 -295 -636 -725 -100 -506 -108 -426 -574 -305 -919 -207 -540 -770 -264 -67 -388 -444 -77 -778 -474 -957 -706 -467 -438 -245 -240 -228 -40 -523 -803 -669 -198 -11 -740 -911 -990 -604 -236 -628 -864 -897 -440 -789 -874 -941 -153 -1 -52 -345 -819 -480 -731 -612 ...
output:
1979
result:
ok single line: '1979'
Test #7:
score: 0
Accepted
time: 1ms
memory: 8200kb
input:
100 50 1 -220 -474 -778 -792 -88 -62 -252 -742 -147 -2 -119 -575 -583 -434 -753 -425 -427 -266 -419 -344 -44 -470 -79 -28 -38 -621 -506 -821 -363 -423 -960 -272 -608 -728 -482 -392 -194 -958 -395 -712 -97 -867 -34 -499 -101 -777 -895 -200 -269 -528 -283 -972 -157 -378 -561 -90 -359 -439 -412 -72 -87...
output:
1433
result:
ok single line: '1433'
Test #8:
score: 0
Accepted
time: 0ms
memory: 9908kb
input:
100 100 1 -100 -438 -107 -887 -504 -162 -557 -696 -551 -955 -634 -230 -109 -3 -754 -669 -775 -685 -517 -137 -80 -419 -207 -131 -554 -26 -864 -981 -282 -925 -704 -457 -186 -975 -730 -174 -294 -176 -664 -385 -625 -894 -93 -156 -737 -541 -265 -906 -403 -445 -41 -260 -609 -828 -60 -800 -750 -6 -239 -846...
output:
981
result:
ok single line: '981'
Test #9:
score: 0
Accepted
time: 39ms
memory: 11504kb
input:
300000 299900 1 975494913 919276412 971822415 306295652 981185393 751782065 954706942 908207836 981200361 32580760 933121007 333012429 165323270 996792016 391102892 389040132 322687143 812406210 317257318 897931477 984765477 903680189 380567163 385513860 359332788 768879270 959852716 843574823 40665...
output:
2999995655
result:
ok single line: '2999995655'
Test #10:
score: 0
Accepted
time: 39ms
memory: 13420kb
input:
300000 299998 1 909963807 988052984 968956733 -4808472 902213296 920535913 892118351 827900769 961754681 767948569 999500834 260018295 349443084 916399438 810195269 870433267 998221337 976774994 721697345 309230801 868119413 986186795 839916169 968333430 270886226 972109273 970633299 744019611 94687...
output:
2999982764
result:
ok single line: '2999982764'
Test #11:
score: 0
Accepted
time: 39ms
memory: 13408kb
input:
300000 199998 1 760358089 791244679 984736604 275806750 247939634 978615072 302237434 991049550 934591187 382618436 230786914 789192758 236573159 396652403 855918715 877242673 984062779 458214751 395632321 988479643 399571663 377064418 969391408 796094553 999200405 268953105 991121067 941437116 8161...
output:
2999990891
result:
ok single line: '2999990891'
Test #12:
score: 0
Accepted
time: 43ms
memory: 13460kb
input:
300000 159999 1 942199382 341392725 348398313 975348962 960975251 991959712 53847869 626494403 440799630 834310895 400767959 364210160 292487754 970542288 975196994 411308866 985283714 134051724 395718459 725662488 484999687 920311363 991679253 970656922 988945259 265707789 986990069 925538439 21784...
output:
2999991601
result:
ok single line: '2999991601'
Test #13:
score: 0
Accepted
time: 39ms
memory: 13496kb
input:
300000 19999 1 816144624 978397453 440665138 283612424 945098204 339820332 885340682 313718676 922094581 381702751 471032137 872210762 240663640 985886109 780872483 996469198 325835675 968745840 794294823 121382252 948969054 880827421 977238043 126375169 950327749 994803525 201684720 219097101 41030...
output:
2999973677
result:
ok single line: '2999973677'
Test #14:
score: 0
Accepted
time: 43ms
memory: 13460kb
input:
300000 100 1 -989312886 26761301 -985728917 -391478114 -78077877 -953591083 -952597776 -966592009 -374175692 -972714759 -865102046 -253636908 -864766148 -877082592 -985097949 -955548975 -946513709 -939137884 -856158829 -878136428 -845660452 -236979816 -198429617 -194522362 -881227475 -934250481 -955...
output:
2999995006
result:
ok single line: '2999995006'
Test #15:
score: 0
Accepted
time: 43ms
memory: 11372kb
input:
300000 2 1 -204526971 -679003931 -270259823 -998170158 -517990818 -331521849 -806999125 -884402567 -394558999 -938154172 -881759024 -205775904 -989396335 -323846513 -902520693 -105353949 -989729701 -999109123 -958206886 -306635474 -650621491 -980044442 -238027623 -916877077 -987985082 -888733152 -92...
output:
2999989700
result:
ok single line: '2999989700'
Test #16:
score: 0
Accepted
time: 38ms
memory: 11408kb
input:
300000 100002 1 -982563248 -884271825 -991717692 -66746774 -387604370 -989101502 -921822473 -452835479 -343905539 -982352212 -334927349 -951113204 -975955017 -816967163 -951729538 -694131066 -367658474 -933012591 -276245389 -456156314 -309453648 -818983958 -832001600 -247724435 -401778387 -287758829...
output:
2999985866
result:
ok single line: '2999985866'
Test #17:
score: 0
Accepted
time: 43ms
memory: 11436kb
input:
300000 140001 1 -981316007 -209123045 -183025883 -382483756 -958956835 -981127429 -996221336 -953952589 -904879391 -283899126 -828187571 -206037038 -961803343 -987393716 -953516223 -348983568 -927817660 281748110 -999551602 -96518828 -400608671 31532273 -872389194 -322196531 -852614563 -441246454 -2...
output:
2999993311
result:
ok single line: '2999993311'
Test #18:
score: 0
Accepted
time: 36ms
memory: 13496kb
input:
300000 280001 1 -913709302 -903985908 -940299999 -205921103 -885171614 -92135108 -977947386 -988415908 -320447615 -795241235 -999358836 -984300628 -406654796 -479470316 -415791878 -966100008 -978511377 -301932359 -356529615 -997674923 -876662022 -887931627 -435841697 -996688996 -985518116 -992611953...
output:
2999990077
result:
ok single line: '2999990077'
Test #19:
score: 0
Accepted
time: 1ms
memory: 7644kb
input:
201 0 2 813 958 277 425 585 853 243 463 433 999 890 615 984 992 363 704 962 349 822 629 44 836 3 832 214 127 816 106 560 570 693 40 934 910 310 674 508 930 995 982 761 429 329 283 602 312 190 67 29 531 847 267 480 956 225 592 466 527 343 809 206 633 364 202 951 581 808 460 940 610 821 725 745 846 12...
output:
-1
result:
ok single line: '-1'
Test #20:
score: 0
Accepted
time: 1ms
memory: 9896kb
input:
201 1 2 641 284 624 715 55 416 598 109 896 957 102 777 343 933 263 245 488 444 65 493 860 504 595 98 856 685 358 523 434 882 835 497 785 526 531 272 781 101 535 501 207 510 945 41 214 770 556 314 87 522 361 517 513 815 969 847 919 867 779 333 727 908 811 228 857 4 153 441 198 419 437 515 664 113 394...
output:
1484
result:
ok single line: '1484'
Test #21:
score: 0
Accepted
time: 1ms
memory: 7988kb
input:
201 2 2 459 848 667 178 587 393 240 592 679 43 323 670 473 484 844 988 243 40 644 657 786 870 33 521 183 523 631 696 701 572 281 306 912 886 915 961 549 538 739 941 706 712 820 506 881 916 266 69 860 84 54 677 945 370 773 681 733 800 312 296 50 953 671 794 356 188 190 390 831 542 433 210 398 57 874 ...
output:
1491
result:
ok single line: '1491'
Test #22:
score: 0
Accepted
time: 1ms
memory: 7892kb
input:
201 100 2 325 812 770 920 500 742 868 298 47 240 521 458 250 991 396 413 314 618 11 192 704 188 187 781 948 611 115 360 890 662 373 612 776 479 368 766 108 209 926 799 636 539 701 762 579 455 312 747 306 21 691 687 904 974 852 994 140 380 625 614 347 29 519 571 518 431 543 914 385 791 765 559 617 27...
output:
1514
result:
ok single line: '1514'
Test #23:
score: -100
Wrong Answer
time: 1ms
memory: 9944kb
input:
201 101 2 363 662 422 678 921 302 192 43 813 948 288 849 3 993 119 59 587 56 605 729 265 42 77 281 417 160 832 717 520 150 379 705 415 106 359 759 507 820 15 523 29 826 37 392 864 140 10 997 767 633 204 498 102 467 447 370 736 439 703 685 535 963 646 928 529 33 816 68 7 566 198 831 752 896 651 593 1...
output:
1496
result:
wrong answer 1st lines differ - expected: '1498', found: '1496'