QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#859751 | #9679. 盒子 | lgvc | 0 | 41ms | 13092kb | C++23 | 1.9kb | 2025-01-17 22:43:23 | 2025-01-17 22:43:24 |
Judging History
answer
#include <bits/stdc++.h>
#define int __int128
static char buf[1000000],*paa=buf,*pd=buf;
static char buf2[1000000],*pp=buf2;
#define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
inline void pc(char ch){
if(pp-buf2==1000000) fwrite(buf2,1,1000000,stdout),pp=buf2;
*pp++=ch;
}
inline void pcc(){
fwrite(buf2,1,pp-buf2,stdout);
pp=buf2;
}
inline int read(void){
int w=1;
register int x(0);register char c(getchar());
while(c<'0'||c>'9'){if(c=='-') w=-1;c=getchar();}
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
return w*x;
}
void write(int x){
static int sta[20];
int top=0;
do{
sta[top++]=x%10,x/=10;
}while(x);
while(top) pc(sta[--top]+48);
}
void we(int x){
write(x);
pc('\n');
}
int T,N,M,K,C,a[1000009],rr[1000009],ff[1000009],su[1000009];
int dp[1000009];
inline int fx(int x) {
return (x%K)*(K-C);
}
signed main(void) {
T=read();
int inf=1;
for(int i=1;i<=36;i++) inf*=10;
while(T--) {
N=read();M=read();K=read();C=read();
int ans=0;
for(int i=1;i<=N;i++) {
a[i]=read();
ans+=a[i];
su[i]=a[i]+su[i-1];
ff[i]=su[i]-su[std::max(i-M,(__int128)0)];
}
for(int i=1;i<=N;i++) {
rr[i]=N+1;
for(int j=i;j<=N;j++) {
if((su[j]-su[i-1]-1)%K+1>ff[j]) {
rr[i]=j;
break;
}
}
}
dp[N+1]=0;
for(int i=N;i>=1;i--) {
dp[i]=inf;
for(int j=i;j<rr[i];j++) {
dp[i]=std::min(dp[i],dp[j+1]+(su[j]-su[i-1])%K*(K-C));
}
int ss=su[rr[i]-1]-su[i-1];
ss%=K;
dp[i]=std::min(dp[i],dp[rr[i]]+C*(K-ss));
}
printf("%lld\n",(long long)((dp[1]+ans*C)/K));
}
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 17
Accepted
time: 0ms
memory: 12112kb
input:
3 5 2 4 3 2 2 1 2 2 4 2 4 3 2 4 1 1 10 3 5 1 2 2 2 2 1 1 1 10 2 2
output:
7 7 6
result:
ok 3 number(s): "7 7 6"
Test #2:
score: 0
Wrong Answer
time: 0ms
memory: 11984kb
input:
65 7 1 27 22 70 29 32 15 69 79 84 10 2 2 1 76 63 99 67 75 30 29 45 79 23 9 1 4 3 47 91 10 30 91 29 12 14 53 10 1 5 4 92 22 92 27 30 50 59 6 57 58 5 2 15 15 59 27 70 24 11 5 2 42 42 70 50 42 55 5 6 2 54 46 67 14 52 80 95 3 10 2 89 88 55 14 45 14 90 81 38 40 54 17 5 2 93 86 35 58 76 64 73 6 1 45 43 63...
output:
308 293 283 395 191 222 271 443 285 338 307 267 348 312 367 427 198 182 316 500 344 190 330 221 262 220 452 243 155 277 482 580 328 360 202 293 222 590 262 460 253 494 523 449 180 222 368 320 360 385 504 494 126 209 220 249 289 210 525 556 168 444 433 430 575
result:
wrong answer 1st numbers differ - expected: '320', found: '308'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #35:
score: 0
Wrong Answer
time: 41ms
memory: 13092kb
input:
66664 7 2 82188055 1 35930054 4923258 36288509 46890418 53350617 49812938 68015568 10 2 460335201 1 305598063 240803174 36008172 416771728 391050572 270293987 333994588 436573185 216917970 103343453 9 3 119910901 1 35106715 29444257 72409421 49339248 23617992 3266647 38704192 75874356 72979434 10 1 ...
output:
5 7 4 12 7 3 7 12 3 4 6 7 7 5 9 10 8 12 4 7 5 8 10 4 3 9 7 4 6 5 6 4 5 9 5 8 3 5 7 11 6 6 13 11 4 6 12 10 7 5 6 5 7 5 3 8 6 5 6 6 7 5 10 6 5 5 6 7 4 8 7 8 6 4 4 5 6 6 6 9 6 10 10 5 4 10 10 6 3 7 5 4 6 7 6 11 4 3 7 9 6 6 5 13 8 13 8 3 4 6 6 5 10 11 6 14 10 8 7 9 6 10 11 6 6 8 7 8 7 4 5 6 10 7 11 3 4 ...
result:
wrong answer 2nd numbers differ - expected: '8', found: '7'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%