QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#859751#9679. 盒子lgvc0 41ms13092kbC++231.9kb2025-01-17 22:43:232025-01-17 22:43:24

Judging History

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

  • [2025-01-17 22:43:24]
  • 评测
  • 测评结果:0
  • 用时:41ms
  • 内存:13092kb
  • [2025-01-17 22:43:23]
  • 提交

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%