Submission #1248855

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int N;
int Array[105];
map <int, int> M;
int DP[105][105][105];
const int MOD = 1000000007;
void Read()
{
    cin >> N;
    for(int i = 1; i <= N * 2 - 1; i++)
        cin >> Array[i];
    sort(Array + 1, Array + N * 2 - 1 + 1);
}
void Add(int& x, int y)
{
    x += y;
    if(x >= MOD)
        x -= MOD;
}
void Solve()
{
    DP[1][1][1] = 1;
    M[Array[N]] = 1;
    int ans = 0;
    int l = N, r = N;
    for(int i = 1; i <= N; i++)
    {
        l--;
        r++;
        int st = 0, cand = 0;
        if(M[Array[l]] == 0)
            st++, cand++;
        if(M[Array[r]] == 0)
            cand++;
        M[Array[l]] = 1;
        M[Array[r]] = 1;
        for(int j = 1; j <= N * 2 - 1; j++)
            for(int k = 1; k <= j; k++)
            {
                if(DP[i][j][k] == 0)
                    continue;
                if(i == N)
                    Add(ans, DP[i][j][k]);
                for(int p = 1; p <= j + cand; p++)
                {
                    if(p < k + st)
                    {
                        Add(DP[i + 1][j + cand - (k + st - p - 1)][p], DP[i][j][k]);
                    }
                    if(p > k + st)
                        Add(DP[i + 1][j + cand - (p - k - st - 1)][k + st + 1], DP[i][j][k]);
                }
                Add(DP[i + 1][j + cand][k + st], DP[i][j][k]);
            }
    }
    cout << ans << "\n";
}
int main()
{
    Read();
    Solve();
    return 0;
}

Submission Info

Judge Result