Submission #13825945

---

Source Code Expand

#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

Judge Result