QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#637179 | #9436. Some Sum of Subset | ucup-team4992# | WA | 1ms | 3840kb | C++20 | 1.1kb | 2024-10-13 10:41:12 | 2024-10-13 10:41:13 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int P=998244353;
int main(){
int n,m;cin>>n>>m;
vector<int>a(n+1);
for(int i=1;i<=n;i++) cin>>a[i];
sort(a.begin()+1,a.end(),greater<int>());
vector<vector<ll>>f(n+1,vector<ll>(n+1));
f[0][0]=1;
for(int i=1;i<=n;i++){
f[i][0]=f[i-1][0]*2;
for(int j=1;j<=n;j++){
f[i][j]=(f[i-1][j]+f[i-1][j-1])%P;
}
}
vector<ll>dp[2];
dp[0].resize(m+10);
dp[1].resize(m+10);
dp[0][0]=1;
int cur=1;
vector<ll>ans(n+1);
vector<ll>tag(n+1);
for(int i=1;i<=n;i++){
dp[cur]=dp[cur^1];
for(int j=0;j<=m;j++){
int k=min(m,j+a[i]);
if(j<m&&k>=m){
tag[i]+=dp[cur^1][j];
tag[i]%=P;
}
dp[cur][k]+=dp[cur^1][j];
dp[cur][k]%=P;
}
// cout<<tag[i]<<'\n';
for(int j=0;j<=n-i;j++){
ans[j]+=tag[i]*f[n-i][j]%P;
ans[j]%=P;
}
cur^=1;
}
for(int i=0;i<=n;i++){
cout<<ans[i]<<'\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3840kb
input:
4 7 3 1 5 2
output:
6 4 1 0 0
result:
ok 5 tokens
Test #2:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
1 5 7
output:
1 0
result:
ok 2 tokens
Test #3:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
9 18 1 9 5 6 2 7 1 4 8
output:
346 309 230 126 46 10 1 0 0 0
result:
ok 10 tokens
Test #4:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
1 1467 556
output:
0 0
result:
ok 2 tokens
Test #5:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
1 1753 2514
output:
1 0
result:
ok 2 tokens
Test #6:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
1 1182 1182
output:
1 0
result:
ok 2 tokens
Test #7:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
2 1741 955 835
output:
1 0 0
result:
ok 3 tokens
Test #8:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
2 1481 2004 1570
output:
3 1 0
result:
ok 3 tokens
Test #9:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
2 1336 1336 1336
output:
3 1 0
result:
ok 3 tokens
Test #10:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
12 400 2163 2729 1322 2787 2404 1068 1502 746 898 2057 1771 502
output:
4095 4083 4017 3797 3302 2510 1586 794 299 79 13 1 0
result:
ok 13 tokens
Test #11:
score: 0
Accepted
time: 1ms
memory: 3816kb
input:
42 1609 532 722 2650 2889 2260 659 1831 401 2779 1262 2185 1479 515 552 1627 637 1080 580 1589 2154 2650 219 2924 1712 311 2609 1062 968 1357 1310 1942 2419 2465 300 2546 2537 2967 1197 2271 1551 999 2531
output:
780135870 780135476 780133126 780115746 779984839 779086101 773744618 746617208 628409426 182368401 707355349 419830171 342550392 778349940 825220795 979080057 177969332 68371210 748001250 187917550 492152134 287983982 592218358 32133349 711757614 602140473 799225822 952989153 1466429 437088327 3596...
result:
ok 43 tokens
Test #12:
score: -100
Wrong Answer
time: 0ms
memory: 3656kb
input:
93 24 1687 2324 1216 2696 2884 1678 1301 1957 1247 526 2519 2252 2141 960 1505 175 315 388 440 892 837 1942 256 1667 641 1629 2565 2837 1200 2427 418 1072 427 1589 969 886 2991 2249 539 1132 949 2425 2616 2107 1259 582 1979 386 177 1860 2825 316 2004 956 1218 2332 1498 2939 1126 1706 404 1604 505 11...
output:
998244352 932051816 10711044 89046951 792318273 838489272 566955198 43888865 483255440 722291523 548143131 339190488 54504286 5405952 64572361 260981990 941743303 658428786 121409046 926769678 140973200 23183677 637382443 890437280 170355920 243899281 940323263 506126351 392145551 3285648 474096654 ...
result:
wrong answer 1st words differ - expected: '958346177', found: '998244352'