Submission #13816717


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

const int64_t MOD = 998244353;
void add(int64_t& a, int64_t b){
    a = (a+b) % MOD;
}
void mul(int64_t& a, int64_t b){
    a = a*b % MOD;
}

int main(){
    int N, S;
    cin >> N >> S;
    vector<int> A(N);
    for(int i=0; i<N; i++) cin >> A[i];
    static int64_t dp[3001][6001];
    dp[0][0] = 1;
    for(int i=0; i<N; i++) for(int j=0; j<=S; j++){
        add(dp[i+1][j+A[i]], dp[i][j]);
        add(dp[i+1][j], 2*dp[i][j]);
    }
    cout << dp[N][S] << endl;
    return 0;
}

Submission Info

Submission Time
Task F - Knapsack for All Subsets
User betrue12
Language C++ (GCC 9.2.1)
Score 600
Code Size 555 Byte
Status AC
Exec Time 100 ms
Memory 97588 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 2 ms 3720 KB
12 AC 3 ms 4520 KB
13 AC 4 ms 4788 KB
14 AC 3 ms 4120 KB
15 AC 2 ms 3588 KB
21 AC 28 ms 27896 KB
22 AC 58 ms 59156 KB
23 AC 53 ms 54612 KB
24 AC 81 ms 80164 KB
25 AC 16 ms 15336 KB
31 AC 44 ms 40940 KB
32 AC 53 ms 49940 KB
33 AC 49 ms 47352 KB
34 AC 53 ms 48612 KB
35 AC 55 ms 48748 KB
41 AC 99 ms 97536 KB
42 AC 100 ms 97588 KB
43 AC 100 ms 97528 KB
44 AC 98 ms 97568 KB
45 AC 99 ms 97476 KB
51 AC 2 ms 3508 KB
52 AC 2 ms 3464 KB
53 AC 22 ms 24284 KB
54 AC 14 ms 15476 KB
sample01 AC 2 ms 3500 KB
sample02 AC 2 ms 3652 KB
sample03 AC 2 ms 3668 KB