QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#153723#6408. Classical Counting Problem275307894aWA 219ms71376kbC++141.1kb2023-08-30 19:45:192023-08-30 19:45:19

Judging History

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

  • [2023-08-30 19:45:19]
  • 评测
  • 测评结果：WA
  • 用时：219ms
  • 内存：71376kb
查看
  • [2023-08-30 19:45:19]
  • 提交

answer

#include<bits/stdc++.h>
#define LB lower_bound
#define PB push_back
#define Me(x,y) memset(x,y,sizeof x)
using namespace std;
using ll=long long;
const int N=200+5,mod=1e9+7;
int n,m,k,x,y,z,A[N],Sum,Ct;ll Ans,f[N][N*N];
void Ins(int x){Sum+=x;Ct++;for(int i=Ct;i;i--) for(int j=x;j<=Sum;j++) f[i][j]=(f[i][j]+f[i-1][j-x])%mod;}
void Del(int x){for(int i=1;i<=Ct;i++) for(int j=x;j<=Sum;j++) f[i][j]=(f[i][j]-f[i-1][j-x]+mod)%mod;Sum-=x;Ct--;}
void Solve(){
    int i,j,h;scanf("%d%d%d",&n,&m,&k);for(i=1;i<=n;i++) scanf("%d",&A[i]);
    sort(A+1,A+n+1);Sum=Ct=0;Me(f,0);f[0][0]=1;
    Ans=0;int R=n;
    for(i=n;i;i--){
        while(R&&A[i]-A[R]<=m) Ins(A[R]),R--;
        Del(A[i]);
        for(j=max(0,k-(n-i));j<=Ct;j++) for(h=max(j*A[i]-m*k,0);h<=Sum;h++) Ans+=f[j][h];
    }
    R=n;for(i=n;i;i--){
        while(R&&A[i]+m<A[R]) Del(A[R]),R--;
        for(j=max(0,n-k-i+2);j<=Ct;j++) for(h=0;h<=Sum&&h<=(A[i]+m)*j-m*(k-(n-j));h++) Ans+=f[j][h];
        Ins(A[i]);
    }
    printf("%lld\n",(Ans+1)%mod);
}
int main(){
    int t;scanf("%d",&t);while(t--) Solve();
    cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 29ms
memory: 71284kb

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: 219ms
memory: 71172kb

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: 160ms
memory: 71328kb

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: 117ms
memory: 71336kb

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: 84ms
memory: 71372kb

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: 42ms
memory: 71340kb

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: 23ms
memory: 71284kb

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: 26ms
memory: 71376kb

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

result:

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

Server Time: 2024-12-03 04:09:42 | OpenSource Project