NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #196439 | #2381. 庆祝会 | wosile | 100 | 8ms | 5132kb | C++11 | 584b | 2023-10-26 08:44:18 | 2023-10-26 12:36:40 |
answer
#include<bits/stdc++.h>
using namespace std;
int n,m;
int f[1005][1005];
int a[1005],pre[1005];
#define mod 998244353
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);
a[n+1]=m+1;
for(int i=1;i<=n+1;i++)pre[i]=pre[i-1]+a[i];
f[n+1][0]=f[n+2][0]=1;
for(int i=n;i>=1;i--){
for(int j=0;j<=m;j++)f[i][j]=f[i+1][j];
for(int j=a[i];j<=m;j++)f[i][j]=(f[i][j]+f[i+1][j-a[i]])%mod;
}
int ans=0;
for(int i=n;i>=0;i--)for(int j=max(0,m-pre[i+1]+1);j<=m-pre[i];j++)ans=(ans+f[i+2][j])%mod;
printf("%d",ans);
return 0;
}
详细
小提示：点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1292kb
input:
19 800 160 65 115 207 17 48 23 201 105 198 40 64 125 213 164 188 131 136 59
output:
9322
result:
ok 1 number(s): "9322"
Test #2:
score: 10
Accepted
time: 0ms
memory: 1296kb
input:
20 886 272 31 202 60 170 112 315 159 96 220 97 22 12 354 131 351 116 294 49 232
output:
4714
result:
ok 1 number(s): "4714"
Test #3:
score: 10
Accepted
time: 0ms
memory: 1296kb
input:
20 534 62 36 59 38 15 58 51 10 69 33 55 80 108 84 30 60 91 60 3 108
output:
28165
result:
ok 1 number(s): "28165"
Test #4:
score: 10
Accepted
time: 0ms
memory: 1612kb
input:
100 92 70 92 34 29 31 65 53 86 32 70 8 49 6 16 33 13 88 87 17 36 81 30 55 37 45 62 21 43 86 3 71 63 ...
output:
695127612
result:
ok 1 number(s): "695127612"
Test #5:
score: 10
Accepted
time: 0ms
memory: 1576kb
input:
92 95 71 17 42 1 28 31 69 76 17 11 18 64 46 36 70 73 52 23 22 59 12 1 86 81 81 28 79 30 57 72 40 29 ...
output:
477279530
result:
ok 1 number(s): "477279530"
Test #6:
score: 10
Accepted
time: 1ms
memory: 1576kb
input:
92 99 19 32 43 1 95 96 91 25 38 85 43 85 81 92 54 81 45 88 91 13 92 75 8 1 8 45 41 65 98 64 89 18 96...
output:
323420510
result:
ok 1 number(s): "323420510"
Test #7:
score: 10
Accepted
time: 0ms
memory: 5128kb
input:
1000 446 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
71062540
result:
ok 1 number(s): "71062540"
Test #8:
score: 10
Accepted
time: 3ms
memory: 5132kb
input:
1000 441 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
269683120
result:
ok 1 number(s): "269683120"
Test #9:
score: 10
Accepted
time: 4ms
memory: 5128kb
input:
1000 641 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
639341583
result:
ok 1 number(s): "639341583"
Test #10:
score: 10
Accepted
time: 0ms
memory: 5116kb
input:
993 995 396 599 552 737 171 773 317 827 21 985 200 652 958 722 792 386 80 343 704 220 821 80 924 1 7...
output:
158912972
result:
ok 1 number(s): "158912972"
Extra Test:
score: 0
Extra Test Passed
