QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #726958 | #8204. 太空飞船 | TheZone | 100 ✓ | 49ms | 10104kb | C++20 | 3.2kb | 2024-11-09 10:39:49 | 2024-11-09 10:39:49 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int M=3e5+5;
int n,k,a[M<<1],b[M<<1],q[M];
ll ans=1ll<<60,f[M],g[M],stk[M];
int read(){
int x=0;char ch=getchar();
while (!isdigit(ch)) ch=getchar();
while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
return x;
}
double slope(int x,int y){return (double)(f[x]-f[y])/(double)(b[x]-b[y]);}
void subtask1(){
for (int i=1;i<=n;i++) a[i+n]=a[i];
for (int i=1;i<=n<<1;i++) b[i]=b[i-1]+a[i];
int res=b[n]/2;
for (int i=1,j=1;i<=n;i++){
while (b[j]-b[i-1]<res) j++; int tmp=b[j]-b[i-1];
ans=min(ans,1ll*tmp*tmp+1ll*(b[n]-tmp)*(b[n]-tmp));
}
printf("%lld\n",1ll*ans*k*k-1ll*b[n]*b[n]*k);
}
void subtask2(){
for (int i=1;i<=n;i++) a[i+n]=a[i];
for (int i=1;i<=n<<1;i++) b[i]=b[i-1]+a[i];
int res=b[n]/3;
for (int i=1,j=1,k=1;i<=n;i++){
while (b[j]-b[i-1]<res) j++;
int tmp1=b[j]-b[i-1],Res=(b[n]-tmp1)/2;
while (b[k]-b[j]<Res) k++; int tmp2=b[k]-b[j];
ans=min(ans,1ll*tmp1*tmp1+1ll*tmp2*tmp2+1ll*(b[n]-tmp1-tmp2)*(b[n]-tmp1-tmp2));
}
printf("%lld\n",1ll*ans*k*k-1ll*b[n]*b[n]*k);
}
void calc(){
for (int i=1;i<=n;i++) b[i]=b[i-1]+a[i];
for (int i=1;i<=n;i++) f[i]=1ll<<60;
for (int T=1;T<=k;T++){
for (int i=1,head=0,tail=0;i<=n;i++){
while (head<tail&&slope(q[head],q[head+1])<b[i]*2.) head++;
g[i]=f[q[head]]-2ll*b[q[head]]*b[i];
while (head<tail&&slope(q[tail-1],q[tail])>slope(q[tail],i)) tail--;
q[++tail]=i;
}
for (int i=1;i<=n;i++) f[i]=g[i]+2ll*b[i]*b[i];
}
ans=min(ans,f[n]-1ll*b[n]*b[n]);
int tmp=a[1];
for (int i=1;i<n;i++) a[i]=a[i+1];
a[n]=tmp;
}
int main(){
n=read();k=read();
for (int i=1;i<=n;i++) a[i]=read();
if (k==2) return subtask1(),0;
if (k==3) return subtask2(),0;
for (int T=1;T<=n;T++) calc();
printf("%lld\n",1ll*ans*k*k-1ll*b[n]*b[n]*k);
return 0;
}
/*#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int M=3e5+5;
int n,k,a[M<<1],b[M<<1],q[M];
ll ans=1ll<<60,f[M],g[M],stk[M];
int read(){
int x=0;char ch=getchar();
while (!isdigit(ch)) ch=getchar();
while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
return x;
}
double slope(int x,int y){return (double)(f[x]-f[y])/(double)(b[x]-b[y]);}
void subtask1(){
for (int i=1;i<=n;i++) a[i+n]=a[i];
for (int i=1;i<=n<<1;i++) b[i]=b[i-1]+a[i];
int res=b[n]/2;
for (int i=1,j=1;i<=n;i++){
while (b[j]-b[i-1]<res) j++; int tmp=b[j]-b[i-1];
ans=min(ans,1ll*tmp*tmp+1ll*(b[n]-tmp)*(b[n]-tmp));
}
printf("%lld\n",1ll*ans*k*k-1ll*b[n]*b[n]*k);
}
void subtask2(){
for (int i=1;i<=n;i++) a[i+n]=a[i];
for (int i=1;i<=n<<1;i++) b[i]=b[i-1]+a[i];
int res=b[n]/3;
for (int i=1,j=1,k=1;i<=n;i++){
while (b[j]-b[i-1]<res) j++;
int tmp1=b[j]-b[i-1],Res=(b[n]-tmp1)/2;
while (b[k]-b[j]<Res) k++; int tmp2=b[k]-b[j];
ans=min(ans,1ll*tmp1*tmp1+1ll*tmp2*tmp2+1ll*(b[n]-tmp1-tmp2)*(b[n]-tmp1-tmp2));
}
for (int T=1;T<=n;T++) calc();
printf("%lld\n",1ll*ans*k*k-1ll*b[n]*b[n]*k);
return 0;
}*/
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 1ms
memory: 5876kb
input:
1000 2 178 616 885 911 62 479 997 921 68 518 328 305 787 733 829 184 628 438 491 87 879 226 9 829 472 245 269 453 490 991 764 843 730 652 194 328 136 590 657 516 945 850 999 812 145 881 100 708 679 463 833 174 337 241 327 580 818 683 550 882 361 831 637 56 228 717 810 326 260 407 795 441 714 276 564...
output:
18
result:
ok 1 number(s): "18"
Test #2:
score: 10
Accepted
time: 3ms
memory: 6664kb
input:
100000 2 890 793 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 900 111 900 900...
output:
236672
result:
ok 1 number(s): "236672"
Test #3:
score: 10
Accepted
time: 0ms
memory: 5888kb
input:
100 3 302 51 544 387 564 786 336 747 191 503 216 689 385 37 988 712 441 723 667 878 653 253 766 18 391 377 378 224 429 101 513 387 878 664 493 483 417 334 975 855 800 992 991 700 541 611 53 22 12 543 328 350 842 635 917 846 772 536 106 569 634 83 147 150 61 118 372 14 599 625 272 699 66 757 714 756 ...
output:
122208
result:
ok 1 number(s): "122208"
Test #4:
score: 10
Accepted
time: 4ms
memory: 6636kb
input:
100000 3 422 758 390 993 755 235 193 741 528 400 512 319 323 427 898 861 667 96 867 555 43 224 258 414 645 568 362 233 721 685 244 783 38 999 146 248 944 19 558 175 883 910 380 483 655 390 142 189 300 667 943 769 360 46 770 849 447 161 924 702 522 320 679 752 27 894 448 96 959 571 659 372 741 156 36...
output:
168
result:
ok 1 number(s): "168"
Test #5:
score: 10
Accepted
time: 10ms
memory: 8520kb
input:
300000 3 827 841 91 956 810 630 921 207 349 704 171 780 32 787 215 864 762 64 500 262 541 316 321 488 174 369 182 601 664 297 913 299 550 672 220 861 713 553 300 647 350 411 541 800 828 374 957 936 20 73 583 914 754 173 536 52 371 624 503 154 871 19 984 175 105 972 194 302 397 99 746 9 154 527 991 7...
output:
54
result:
ok 1 number(s): "54"
Test #6:
score: 10
Accepted
time: 1ms
memory: 9932kb
input:
50 6 968 270 819 103 585 639 684 406 451 481 811 674 731 384 206 738 56 917 917 783 888 868 366 204 510 377 946 160 378 119 881 675 992 481 949 447 806 21 590 361 457 621 761 960 935 936 855 542 283 545
output:
1137054
result:
ok 1 number(s): "1137054"
Test #7:
score: 10
Accepted
time: 2ms
memory: 9952kb
input:
100 7 56 565 399 452 934 357 416 674 280 323 586 864 657 150 802 115 246 110 579 589 195 637 783 990 574 52 452 19 44 227 603 543 682 769 141 456 543 965 151 947 833 52 920 346 213 76 417 333 435 112 676 23 793 293 647 218 142 380 883 829 74 594 768 421 957 788 996 818 989 487 660 756 212 454 386 69...
output:
3312988
result:
ok 1 number(s): "3312988"
Test #8:
score: 10
Accepted
time: 3ms
memory: 9980kb
input:
200 10 144 860 212 801 516 75 916 174 341 165 592 53 814 149 166 723 435 71 472 163 733 639 967 544 638 727 727 111 710 568 92 179 604 57 334 465 512 910 713 301 209 482 311 732 723 217 210 124 587 911 949 41 86 797 475 121 103 117 98 218 647 540 145 394 186 919 968 663 528 673 630 585 121 292 1 853...
output:
28576560
result:
ok 1 number(s): "28576560"
Test #9:
score: 10
Accepted
time: 21ms
memory: 10104kb
input:
300 15 777 732 780 214 534 720 85 991 259 526 955 108 173 214 431 995 929 498 392 315 430 32 964 588 782 12 409 642 689 851 659 156 131 34 159 639 975 128 623 545 148 825 998 259 39 541 935 398 337 432 265 849 234 523 894 33 573 35 676 11 22 433 891 350 394 474 760 549 118 816 385 987 67 176 378 447...
output:
58640310
result:
ok 1 number(s): "58640310"
Test #10:
score: 10
Accepted
time: 49ms
memory: 9996kb
input:
400 20 950 342 309 617 918 460 205 917 406 359 116 443 653 202 968 410 259 995 116 938 628 322 318 146 76 303 650 118 260 915 869 291 812 658 349 982 626 336 935 457 962 754 448 584 750 742 360 380 735 229 660 877 205 279 667 629 99 944 444 274 967 122 918 788 217 803 231 153 529 544 745 285 214 827...
output:
211034400
result:
ok 1 number(s): "211034400"