QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#113263#6408. Classical Counting ProblemSoyTonyWA 87ms3904kbC++143.2kb2023-06-16 20:07:482023-06-16 20:08:19

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-16 20:08:19]
  • 评测
  • 测评结果：WA
  • 用时：87ms
  • 内存：3904kb
查看
  • [2023-06-16 20:07:48]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

const int maxn=105;
const int lim=10000;
const int maxw=10005;
const int mod=998244353;

inline int read(){
    int x=0,w=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*w;
}

int t;
int n,m,v;
int a[maxn];
int dp[2][maxw],f[maxn][maxn],g[maxn][maxn];
int ans;
int main(){
    // freopen("test.in","r",stdin);
    // freopen("test.out","w",stdout);
    t=read();
    while(t--){
        n=read(),m=read(),v=read();
        for(int i=1;i<=n;++i) a[i]=read();
        sort(a+1,a+n+1,[&](int x,int y){
            return x>y;
        });
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
                f[i][j]=g[i][j]=0;
            }
        }
        for(int x=1;x<=n;++x){
            // cerr<<"x:"<<x<<endl;
            for(int j=0;j<=lim;++j) dp[0][j]=dp[1][j]=0;
            dp[0][0]=1;
            for(int i=x+1,k=1;i<=n;++i,k^=1){
                // cerr<<"i:"<<i<<endl;
                if(a[i]+m<a[x]) break;
                for(int j=0;j<=lim;++j){
                    if(j+a[x]-a[i]>m*v&&dp[k^1][j]){
                        f[x][i]=(f[x][i]+dp[k^1][j])%mod;
                        // cerr<<"j:"<<j<<" a[x]-a[i]:"<<a[x]-a[i]<<" dp:"<<dp[k^1][j]<<endl;
                    }
                }
                // cerr<<"f(x,i):"<<f[x][i]<<endl;
                for(int j=0;j<=lim;++j){
                    if(j>=0) dp[k][j]=(dp[k][j]+dp[k^1][j])%mod;
                    if(j-(a[x]-a[i])>=0) dp[k][j]=(dp[k][j]+(dp[k^1][j-(a[x]-a[i])]))%mod;
                    if(dp[k][j]){
                        // cerr<<"j:"<<j<<" dp:"<<dp[k][j]<<endl;
                    }
                }
                for(int j=0;j<=lim;++j) dp[k^1][j]=0;
            }
        }
        for(int y=1;y<=n;++y){
            // cerr<<"y:"<<y<<endl;
            for(int j=0;j<=lim;++j) dp[0][j]=dp[1][j]=0;
            dp[0][0]=1;
            for(int i=y-1,k=1;i>=1;--i,k^=1){
                cerr<<"i:"<<i<<endl;
                if(a[y]+m<a[i]) break;
                for(int j=0;j<=lim;++j){
                    if(j==0) cerr<<j+(a[y]+m-a[i])+m*(n-y+i)<<" "<<dp[k^1][j]<<endl;
                    if(j+(a[y]+m-a[i])+m*(n-y+i)>=m*v&&dp[k^1][j]){
                        g[y][i]=(g[y][i]+dp[k^1][j])%mod;
                        // cerr<<"j:"<<j<<" a[y]+m-a[i]:"<<a[y]+m-a[i]<<" m*(n-y+j):"<<m*(n+y-j)<<" dp:"<<dp[k^1][j]<<endl;
                    }
                }
                // cerr<<"g(y,i):"<<f[y][i]<<endl;
                for(int j=0;j<=lim;++j){
                    if(j-m>=0) dp[k][j]=(dp[k][j]+dp[k^1][j-m])%mod;
                    if(j-(a[y]+m-a[i])>=0) dp[k][j]=(dp[k][j]+dp[k^1][j-(a[y]+m-a[i])])%mod;
                    if(dp[k][j]){
                        // cerr<<"j:"<<j<<" dp:"<<dp[k][j]<<endl;
                    }
                }
                for(int j=0;j<=lim;++j) dp[k^1][j]=0;
            }
        }
        ans=0;
        for(int x=1;x<=n;++x){
            for(int y=x+1;y<=n;++y){
                ans=(ans+g[y][x]-f[x][y]+mod)%mod;
            }
        }
        ans=(ans+n)%mod;
        printf("%d\n",ans);
    }   
    return 0;
}
源文件, 语言: C++14

詳細信息

Test #1:

score: 100
Accepted
time: 6ms
memory: 3724kb

input:

6
3 1 2
1 2 3
3 2 1
1 2 3
10 1 1
0 0 0 0 0 0 0 0 0 0
6 1 2
2 1 1 3 0 2
6 1 5
2 1 1 3 0 2
10 4 8
7 2 3 6 1 6 5 4 6 5

output:

5
6
1023
23
19
240

result:

ok 6 numbers

Test #2:

score: 0
Accepted
time: 6ms
memory: 3660kb

input:

50
2 62 1
67 58
2 23 1
7 39
2 60 1
53 9
2 29 1
3 68
2 52 1
43 76
2 79 1
48 91
2 85 1
18 11
2 34 1
19 24
2 42 1
77 44
2 54 1
80 49
2 90 1
61 55
2 24 1
51 72
2 8 1
9 8
2 83 1
91 0
2 33 1
27 27
2 30 1
8 99
2 52 1
34 87
2 51 1
13 47
2 16 1
0 27
2 63 1
53 76
2 25 1
82 36
2 42 1
53 54
2 12 1
38 70
2 2 1
6...

output:

3
2
3
2
3
3
3
3
3
3
3
3
3
2
3
2
2
3
2
3
2
3
2
2
2
3
3
2
3
3
3
2
2
2
3
3
3
2
3
2
3
3
3
3
3
3
3
3
3
3

result:

ok 50 numbers

Test #3:

score: 0
Accepted
time: 4ms
memory: 3704kb

input:

40
2 20 1
36 90
4 4 3
38 52 64 63
2 89 1
46 65
2 2 1
83 1
3 17 2
19 20 10
2 61 1
33 17
2 91 1
92 59
2 98 1
4 35
2 30 1
66 51
2 4 1
44 16
2 46 1
80 99
3 11 2
80 59 29
3 91 1
80 43 81
2 93 1
74 57
2 78 1
30 77
3 84 1
70 12 29
2 74 1
88 78
3 58 1
22 100 13
3 40 2
79 18 84
4 99 1
32 73 81 73
2 57 1
83 3...

output:

2
5
3
2
6
3
3
3
3
2
3
3
7
3
3
6
3
4
4
15
3
7
2
4
5
2
3
3
2
2
7
3
2
3
3
15
3
3
2
7

result:

ok 40 numbers

Test #4:

score: 0
Accepted
time: 15ms
memory: 3872kb

input:

30
3 82 1
18 19 77
4 22 1
63 42 11 42
2 60 1
25 90
3 87 2
21 47 5
2 50 1
88 81
4 71 1
63 29 19 68
6 69 3
13 4 71 96 73 39
3 83 2
29 88 28
2 56 1
84 20
2 43 1
8 29
2 48 1
43 9
3 88 1
12 88 58
6 42 4
16 33 47 70 66 42
7 71 1
95 96 18 92 9 20 4
3 11 1
64 46 83
2 7 1
72 49
2 35 1
15 24
3 50 2
82 22 48
4...

output:

6
7
2
7
3
12
39
7
2
3
3
6
38
22
3
2
3
5
6
7
7
3
18
2
55
3
4
3
7
7

result:

ok 30 numbers

Test #5:

score: 0
Accepted
time: 10ms
memory: 3716kb

input:

20
7 41 6
9 17 92 61 58 10 96
2 97 1
84 29
2 83 1
52 65
4 28 3
28 81 53 74
9 69 5
10 80 90 1 91 21 81 96 60
3 66 1
21 9 24
7 88 6
34 21 5 100 51 68 88
2 49 1
62 7
2 6 1
10 1
6 21 1
54 0 16 8 61 16
3 22 2
10 13 75
5 20 1
77 4 16 16 38
5 26 4
31 14 85 69 20
3 31 2
36 58 78
11 39 6
47 7 79 15 34 99 29 ...

output:

20
3
3
8
91
7
43
2
2
15
4
9
10
5
117
3
82
15
545
7

result:

ok 20 numbers

Test #6:

score: 0
Accepted
time: 47ms
memory: 3764kb

input:

10
6 32 4
3 64 60 50 71 92
5 17 3
34 22 90 94 35
46 34 44
33 32 55 85 54 4 8 56 87 90 86 88 6 76 12 76 31 80 58 70 99 92 13 59 82 20 25 97 29 64 16 39 57 40 19 17 48 86 6 60 89 99 71 83 95 6
3 62 1
60 0 96
11 85 7
79 92 34 24 79 36 75 89 78 60 5
3 91 2
55 18 29
12 41 5
75 4 81 73 71 93 50 10 43 55 6...

output:

24
10
85407
5
1426
7
647
2
6
19

result:

ok 10 numbers

Test #7:

score: 0
Accepted
time: 65ms
memory: 3904kb

input:

5
40 23 31
75 10 19 30 90 96 40 84 96 20 44 61 24 46 39 56 1 73 54 83 85 3 13 14 45 46 39 99 91 99 48 89 28 75 62 5 24 51 61 11
16 62 2
96 5 95 8 67 28 36 20 20 48 89 64 11 50 56 38
15 53 7
43 10 69 97 98 99 38 88 78 74 57 69 0 78 61
27 67 6
74 37 76 8 74 42 76 6 68 94 49 55 10 28 35 25 17 41 65 85 ...

output:

26111
2098
2839
2739716
3

result:

ok 5 number(s): "26111 2098 2839 2739716 3"

Test #8:

score: -100
Wrong Answer
time: 87ms
memory: 3688kb

input:

4
17 100 14
65 87 80 62 80 85 47 14 13 23 91 39 5 82 59 28 46
14 83 8
46 14 88 24 70 57 14 6 63 18 98 68 20 10
40 94 16
91 33 82 64 50 16 2 64 39 76 75 35 20 0 53 14 74 2 44 83 51 67 97 93 61 77 56 12 29 95 77 7 78 46 85 76 76 38 22 94
29 3 5
27 14 12 21 45 42 2 41 92 27 54 46 15 73 38 99 68 96 79 1...

output:

40145
8703
159346709
64

result:

wrong answer 3rd numbers differ - expected: '880766959', found: '159346709'
English 繁體中文 简体中文

伺服器時間: 2024-12-02 22:44:32 | 開源專案