Submission #13826334


Source Code Expand

Copy
#include <iostream>
#include <vector>
#include <algorithm>
using i64 = long long;

constexpr auto pow(long long x, long long n, const long long mod) {
    long long ret = 1;
    while(n > 0) {
        if ((n & 1) == 1) ret = (ret * x) % mod;
        x = (x * x) % mod;
        n >>= 1;
    }
    return ret;
}

constexpr auto inverse(const long long x, const long long p) {
    return pow(x, p - 2, p);
}

int main() {
    constexpr i64 mod = 998244353;
    int n, s;
    std::cin >> n >> s;
    std::vector<int> a(n);
    for (auto &e : a) std::cin >> e;

    const i64 inv = inverse(2, mod);
    std::vector<i64> dp(s + 1);
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        auto next(dp);
        for (int j = 0; j + a[i] <= s; j++) {
            next[j + a[i]] = (next[j + a[i]] + dp[j] * inv % mod) % mod;
        }
        std::swap(dp, next);
    }

    std::cout << dp.back() * pow(2, n, mod) % mod << std::endl;

    return 0;
}

Submission Info

Submission Time
Task F - Knapsack for All Subsets
User CharlotteL
Language C++ (GCC 9.2.1)
Score 600
Code Size 985 Byte
Status AC
Exec Time 30 ms
Memory 3656 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 8 ms 3424 KB
12 AC 2 ms 3628 KB
13 AC 2 ms 3584 KB
14 AC 2 ms 3628 KB
15 AC 2 ms 3500 KB
21 AC 4 ms 3500 KB
22 AC 11 ms 3620 KB
23 AC 7 ms 3580 KB
24 AC 8 ms 3656 KB
25 AC 3 ms 3460 KB
31 AC 14 ms 3520 KB
32 AC 17 ms 3656 KB
33 AC 19 ms 3468 KB
34 AC 17 ms 3632 KB
35 AC 17 ms 3604 KB
41 AC 25 ms 3632 KB
42 AC 25 ms 3544 KB
43 AC 29 ms 3652 KB
44 AC 30 ms 3492 KB
45 AC 26 ms 3548 KB
51 AC 2 ms 3480 KB
52 AC 2 ms 3532 KB
53 AC 3 ms 3504 KB
54 AC 3 ms 3448 KB
sample01 AC 2 ms 3596 KB
sample02 AC 4 ms 3600 KB
sample03 AC 2 ms 3592 KB