Submission #13825945


Source Code Expand

Copy
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 200005

int main() {
    ll n, s;
    cin >> n >> s;
    ll a[n];
    rep(i,n)cin >> a[i];
    ll MOD = 998244353;

    ll dp[n][4000];
    rep(i,n)rep(j,4000)dp[i][j] = 0;

    rep(i,n){
        if(i == 0){
            dp[0][0] = 2;
            dp[0][a[i]] = 1;
        }else{
            rep(j,4000){
                dp[i][j] = dp[i-1][j] * 2 % MOD;
            }
            rep(j,4000){
                if(j + a[i] < 4000){
                    dp[i][j+a[i]] += dp[i-1][j];
                    dp[i][j+a[i]] %= MOD;
                }
            }
        }
    }

    cout << dp[n-1][s] << endl;
    return 0;
}


Submission Info

Submission Time
Task F - Knapsack for All Subsets
User Shibuyap
Language C++ (GCC 9.2.1)
Score 600
Code Size 958 Byte
Status AC
Exec Time 86 ms
Memory 97360 KB

Judge Result

Set Name sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 27
Set Name Test Cases
sample sample01, sample02, sample03
All 11, 12, 13, 14, 15, 21, 22, 23, 24, 25, 31, 32, 33, 34, 35, 41, 42, 43, 44, 45, 51, 52, 53, 54, sample01, sample02, sample03
Case Name Status Exec Time Memory
11 AC 5 ms 4236 KB
12 AC 8 ms 6056 KB
13 AC 3 ms 6100 KB
14 AC 4 ms 5308 KB
15 AC 2 ms 3740 KB
21 AC 69 ms 82864 KB
22 AC 44 ms 51248 KB
23 AC 48 ms 57104 KB
24 AC 81 ms 94088 KB
25 AC 16 ms 17116 KB
31 AC 82 ms 97316 KB
32 AC 82 ms 95436 KB
33 AC 80 ms 95264 KB
34 AC 83 ms 97152 KB
35 AC 85 ms 96512 KB
41 AC 82 ms 97324 KB
42 AC 85 ms 97360 KB
43 AC 82 ms 97296 KB
44 AC 81 ms 97192 KB
45 AC 84 ms 97208 KB
51 AC 2 ms 3584 KB
52 AC 2 ms 3612 KB
53 AC 86 ms 97132 KB
54 AC 83 ms 97292 KB
sample01 AC 2 ms 3616 KB
sample02 AC 2 ms 3548 KB
sample03 AC 2 ms 3904 KB