Submission #1369710

---

Source Code Expand

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

#define int long long

#define inf 1000000007LL
#define mod 1000000007LL

#define rep(i, n) for(int i = 0; i < (n); i++)
#define trep(i, n) for(int i = 0; i <= (n); i++)
#define rrep(i, n) for(int i = (n) - 1; i >= 0; i--)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define mfor(i, s, t) for(int i = (s); i < (t); i++)
#define tfor(i, s, t) for(int i = (s); i <= (t); i++)
#define rfor(i, s, t) for(int i = (t) - 1; i >= (s); i--)


int d[114];

int dp[55][114][114];

signed main() {
  int n;
  cin >> n;
  rep(i, 2 * n - 1) {
    cin >> d[i];
  }
  sort(d, d + 2 * n - 1);
  rep(i, n) {
    rep(j, 2 * n) {
      rep(k, 2 * n) {
        dp[i][j][k] = 0;
      }
    }
  }
  dp[0][1][0] = 1;
  rep(i, n - 1) {
    int p, a;
    if(d[n - 1 - i] == d[n - 1 - i - 1]) {
      p = 0;
    }
    else {
      p = 1;
    }
    if(d[n - 1 + i] == d[n - 1 + i + 1]) {
      a = 0;
    }
    else {
      a = 1;
    }
    rep1(j, i * 2 + 1) {
      rep(k, j) {
        rep(_, j + p + a) {
          if(_ < k + p) {
            dp[i + 1][j + p + a - ((k + p) - _ - 1)][_] = (dp[i + 1][j + p + a - ((k + p) - _ - 1)][_] + dp[i][j][k]) % inf;
          }
          else if(_ == k + p) {
            dp[i + 1][j + p + a][_] = (dp[i + 1][j + p + a][_] + dp[i][j][k]) % inf;
          }
          else {
            dp[i + 1][j + p + a - (_ - (k + p) - 1)][k + p + 1] = (dp[i + 1][j + p + a - (_ - (k + p) - 1)][k + p + 1] + dp[i][j][k]) % inf;
          }
        }
      }
    }
  }
  int all = 0;
  rep(j, 2 * n) {
    rep(k, 2 * n) {
      all = (all + dp[n - 1][j][k]) % inf;
    }
  }
  cout << all << endl;
}

Submission Info

Judge Result