QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#153723	#6408. Classical Counting Problem	275307894a	WA	219ms	71376kb	C++14	1.1kb	2023-08-30 19:45:19	2023-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';
}

源文件, 语言: C++14

詳細信息

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:

result:

ok 6 numbers

Test #2:

score: 0

Accepted

time: 219ms

memory: 71172kb

input:

output:

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:

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:

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:

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:

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:

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:

result:

wrong answer 3rd numbers differ - expected: '880766959', found: '36297385'