QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#859758 | #9679. 盒子 | lgvc | 0 | 33ms | 12620kb | C++23 | 1.9kb | 2025-01-17 22:58:02 | 2025-01-17 22:58:03 |
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+1,(__int128)0)];
}
for(int i=1;i<=N;i++) {
rr[i]=N;
for(int j=i;j<=N&&ff[j]<=K;j++) {
if((su[j]-su[i-1])%K>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]]-su[i-1];
ss%=K;
dp[i]=std::min(dp[i],dp[rr[i]+1]+C*(K-ss));
}
printf("%lld\n",(long long)((dp[1]+ans*C)/K));
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 17
Accepted
time: 0ms
memory: 12108kb
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: 12120kb
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:
320 293 287 398 191 222 271 445 285 344 307 267 348 312 367 427 199 182 316 502 344 197 330 233 262 220 452 243 155 280 482 580 328 373 202 293 228 590 268 475 246 494 523 476 186 223 368 323 361 392 507 494 132 209 224 250 297 216 525 556 172 444 433 430 578
result:
wrong answer 12th numbers differ - expected: '270', found: '267'
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: 33ms
memory: 12620kb
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 8 4 13 8 3 8 13 3 4 6 10 8 5 11 13 9 14 5 7 5 11 11 4 3 9 7 4 6 5 6 4 5 12 5 9 3 5 10 12 6 6 14 15 4 7 14 14 7 5 7 6 9 5 3 10 8 8 7 6 7 5 11 6 6 5 6 7 4 9 9 9 6 4 3 5 7 6 6 13 6 10 12 5 4 10 14 7 3 7 5 4 7 9 8 13 4 4 8 10 6 6 6 15 10 15 11 3 4 6 7 5 11 13 6 16 13 8 7 10 7 14 11 7 6 9 10 10 8 4 5 7...
result:
wrong answer 75th numbers differ - expected: '4', found: '3'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%