Submission #13824819

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    int N, S;
    cin >> N >> S;
    vector<ll> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    
    
    ll mod = 998244353;
    vector<vector<ll>> dp(N+1, vector<ll>(S+1, 0));
    dp[0][0] = 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= S; j++) {
            dp[i][j] %= mod;
            dp[i+1][j] += dp[i][j]*2%mod;
            if (j+A[i] <= S) dp[i+1][j+A[i]] += dp[i][j];
        }
    }
    cout << dp[N][S] % mod << endl;
    return 0;
}

Submission Info

Submission Time
Task F - Knapsack for All Subsets
User hitoare
Language C++ (GCC 9.2.1)
Score 600
Code Size 576 Byte
Status AC
Exec Time 72 ms
Memory 73652 KiB

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 2 ms 3716 KiB
12 AC 2 ms 3744 KiB
13 AC 2 ms 3656 KiB
14 AC 2 ms 3624 KiB
15 AC 2 ms 3632 KiB
21 AC 6 ms 6204 KiB
22 AC 34 ms 34852 KiB
23 AC 29 ms 28340 KiB
24 AC 36 ms 37624 KiB
25 AC 11 ms 8648 KiB
31 AC 31 ms 28704 KiB
32 AC 38 ms 37792 KiB
33 AC 35 ms 35468 KiB
34 AC 37 ms 36432 KiB
35 AC 39 ms 36364 KiB
41 AC 70 ms 73592 KiB
42 AC 72 ms 73512 KiB
43 AC 72 ms 73652 KiB
44 AC 70 ms 73616 KiB
45 AC 70 ms 73620 KiB
51 AC 2 ms 3504 KiB
52 AC 6 ms 3644 KiB
53 AC 3 ms 3784 KiB
54 AC 3 ms 3788 KiB
sample01 AC 2 ms 3500 KiB
sample02 AC 2 ms 3556 KiB
sample03 AC 2 ms 3424 KiB