Submission #3414066

---

Source Code Expand

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

/*
templates for competitive programming
type long long -> type ll 
define constants : EPS, INF, MOD, PI
define macros : REP, FOR, ALL, SORT, REVERSE
define number theory functions: qp(a, b), qp(a, b, mo), gcd(a, b)
define dx, dy
*/
   typedef long  ll;

   const double EPS = (1e-7);
   const int INF =(1e9);
   const double PI = (acos(-1));
   const int MOD = (int(1e9) + 7);

   #define REP(i, n) for(int i = 0; i < (int)(n); i++)
   #define FOR(i, a, b) for (int i = (a); i < (b); i++)
   #define ALL(x) (x).begin(),(x).end()
   #define SORT(x) sort((x).begin(), (x).end())
   #define REVERSE(x) reverse((x).begin(), (x).end())
   #define SZ(x) ((int)(x).size())


   #define dump(x) cerr<< #x << "= " << (x) << endl;

   int gcd(int a,int b){return b?gcd(b,a%b):a;};
   ll power(ll a, ll b){
       if (b == 0) return 1;
       else if (b % 2 == 0) return power(a * a, b / 2);
       else return a * power(a, b - 1);
   }

   int dx[4]={1,0,-1,0};
   int dy[4]={0,1,0,-1};


void solve() {
}

int main() {
   cin.tie(0);
   ios::sync_with_stdio(false);
   int n, a;
   cin >> n >> a;
   vector<int> x(n);
   REP(i, n){
       int xi;
       cin >> xi;
       x[i] = xi - a;
   }
   vector<int> x_plus;
   vector<int> x_minus;
   int x_zero = 0;
   REP(i, n){
       if (x[i] > 0){
           x_plus.push_back(x[i]);
       }
       else if (x[i] < 0){
           x_minus.push_back(- x[i]);
       }
       else{
           x_zero ++;
       }
   }
   const int MAX_S = 50 * 50;
   vector<ll> s_plus(MAX_S);
   vector<ll> s_minus(MAX_S);
   s_plus[0] = s_minus[0] = 1;

   REP(i, x_plus.size()){
       for(int j = MAX_S; j > 0; j--){
           if (j >= x_plus[i]){
               s_plus[j] += s_plus[j - x_plus[i]];
           }
       }
   }
    REP(i, x_minus.size()){
        for(int j = MAX_S; j > 0; j--){
            if (j >= x_minus[i]){
                s_minus[j] += s_minus[j - x_minus[i]];
            }
        }
    }
    ll ans = 0;
    REP(i, MAX_S){
        ans += s_plus[i] * s_minus[i];
    }
    ans *= pow(2, x_zero);
    cout << ans - 1 << endl;

}

Submission Info

Judge Result