QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#408076#6408. Classical Counting Problemgrass8cow#WA 64ms8160kbC++171.0kb2024-05-09 17:43:012024-05-09 17:43:02

Judging History

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

  • [2024-05-09 17:43:02]
  • 评测
  • 测评结果：WA
  • 用时：64ms
  • 内存：8160kb
查看
  • [2024-05-09 17:43:01]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n,m,a[110],v;
const int mod=998244353;
int dp[110][10010];
void del(int x){
    for(int i=1;i<=n;i++)for(int j=x;j<=i*100;j++)
    (dp[i][j]-=dp[i-1][j-x])%=mod;
}
void ins(int x){
    for(int i=n;i;i--)for(int j=i*100;j>=x;j--)
    (dp[i][j]+=dp[i-1][j-x])%=mod;
}
int sol(int fl){
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    int ans=0;
    for(int i=1,j=1;i<=n;i++){
        while(j<i&&a[i]-a[j]>m)del(a[j++]);
        for(int z=0;z<=n;z++)if(z+(n-i)>=v+fl)for(int h=0;h<=z*100;h++)if(dp[z][h])
            if(a[i]*z-h<=m*v)
            (ans+=dp[z][h])%=mod;
        ins(a[i]);
    }
    return ans;
}
void sol(){
    scanf("%d%d%d",&n,&m,&v);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    int ans=1;
    (ans+=sol(0))%=mod;
    reverse(a+1,a+n+1);for(int i=1;i<=n;i++)a[i]=100-a[i];
    v=n-v;
    (ans+=sol(1))%=mod;
    printf("%d\n",ans);
}
int main(){
    int T;scanf("%d",&T);while(T--)sol();
    return 0;
}
源文件, 语言: C++17

详细

Test #1:

score: 100
Accepted
time: 5ms
memory: 8088kb

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: 14ms
memory: 8084kb

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: 11ms
memory: 8124kb

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: 11ms
memory: 8148kb

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: 6ms
memory: 8112kb

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: 27ms
memory: 8148kb

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: 24ms
memory: 8152kb

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: 0
Accepted
time: 22ms
memory: 8160kb

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
880766959
64

result:

ok 4 number(s): "40145 8703 880766959 64"

Test #9:

score: -100
Wrong Answer
time: 64ms
memory: 8144kb

input:

3
64 81 26
6 35 9 39 70 29 91 9 54 21 83 73 10 93 96 40 50 92 88 87 71 70 22 45 4 23 18 10 88 71 73 5 49 67 12 28 8 61 73 19 27 89 64 65 94 93 87 61 40 4 37 66 72 100 54 33 80 40 26 46 85 59 1 50
26 6 12
56 37 5 5 3 67 52 53 77 55 39 89 86 55 78 34 83 78 75 51 9 43 2 18 86 14
10 89 1
10 41 16 63 14 ...

output:

-74513956
139
230

result:

wrong answer 1st numbers differ - expected: '923730397', found: '-74513956'
English 繁體中文 简体中文

服务器时间: 2024-12-12 00:00:22 | 开源项目