Submission #1175608

---

Source Code Expand

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
typedef long long lli;
lli n,x;
vector<lli> w;
vector<unordered_map<lli,lli> > dp;
lli ans = 0;
int main(){
    cin >> n >> x;
    w = vector<lli> (n);
    for(lli i = 0;i < n;i++) cin >> w[i];
    dp = vector<unordered_map<lli,lli> > (n+2);
    dp[0][0] = 1;
    dp[n+1][0] = 1;
    for(lli i = 0;i < n/2;i++){
        for(auto itr = dp[i].begin();itr != dp[i].end();itr++){
            dp[i+1][itr->first] += dp[i][itr->first];
            dp[i+1][itr->first+w[i]] += dp[i][itr->first];
        }
    }
    for(lli i = n+1;i > n/2+1;i--){
        for(auto itr = dp[i].begin();itr != dp[i].end();itr++){
            dp[i-1][itr->first] += dp[i][itr->first];
            dp[i-1][itr->first+w[i-2]] += dp[i][itr->first];
        }
    }
    for(auto itr = dp[n/2].begin();itr != dp[n/2].end();itr++){
        ans += dp[n/2+1][x - itr->first] * itr->second;
    }
    cout << ans << endl;
    return 0;
} 

Submission Info

Judge Result