Submission #13806458


Source Code Expand

Copy
#include<bits/stdc++.h>

using namespace std;

#define int long long
int mod = 998244353;
int const maxn = 3005;
int a[maxn], dp[maxn][maxn];

main() {
#ifdef HOME
    freopen("input.txt", "r", stdin);
#endif // HOME
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, s;
    cin >> n >> s;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= s; ++j) {
            if (j < a[i]) dp[i][j] = dp[i - 1][j] * 2 % mod;
            else {
                dp[i][j] = (dp[i - 1][j] * 2 + dp[i - 1][j - a[i]]) % mod;
            }
        }
    }
    cout << dp[n][s] << '\n';
    return 0;
}

Submission Info

Submission Time
Task F - Knapsack for All Subsets
User traktor74
Language C++ (GCC 9.2.1)
Score 600
Code Size 719 Byte
Status AC
Exec Time 116 ms
Memory 74048 KB

Compile Error

./Main.cpp:10:6: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type]
   10 | main() {
      |      ^

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 KB
12 AC 3 ms 4220 KB
13 AC 5 ms 4428 KB
14 AC 3 ms 3932 KB
15 AC 2 ms 3660 KB
21 AC 16 ms 16476 KB
22 AC 58 ms 39392 KB
23 AC 49 ms 35436 KB
24 AC 66 ms 49560 KB
25 AC 15 ms 10772 KB
31 AC 51 ms 40928 KB
32 AC 65 ms 49932 KB
33 AC 62 ms 47396 KB
34 AC 61 ms 48608 KB
35 AC 68 ms 48700 KB
41 AC 114 ms 74008 KB
42 AC 114 ms 74040 KB
43 AC 116 ms 74000 KB
44 AC 113 ms 74040 KB
45 AC 113 ms 74048 KB
51 AC 4 ms 3516 KB
52 AC 2 ms 3520 KB
53 AC 13 ms 15548 KB
54 AC 14 ms 15644 KB
sample01 AC 2 ms 3552 KB
sample02 AC 2 ms 3676 KB
sample03 AC 2 ms 3644 KB