Submission #1319762


Source Code Expand

// Copyright (C) 2017 __debug.

// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation; version 3

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program; If not, see <http://www.gnu.org/licenses/>.


#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>

#define x first
#define y second
#define MP std::make_pair
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif

using std::pair;
using std::vector;
using std::string;

typedef long long LL;
typedef pair<int, int> Pii;

const int oo = 0x3f3f3f3f;

template<typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, true : false; }
template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, true : false; }
string procStatus()
{
    std::ifstream t("/proc/self/status");
    return string(std::istreambuf_iterator<char>(t), std::istreambuf_iterator<char>());
}
template<typename T> T read(T &x)
{
    int f = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar())
        f = (ch == '-' ? -1 : 1);
    for (x = 0; isdigit(ch); ch = getchar())
        x = 10 * x + ch - '0';
    return x *= f;
}
template<typename T> void write(T x)
{
    if (x == 0) {
        putchar('0');
        return;
    }
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    static char s[20];
    int top = 0;
    for (; x; x /= 10)
        s[++top] = x % 10 + '0';
    while (top)
        putchar(s[top--]);
}
// EOT

const int MAXN = 105;
const int MOD = 1e9 + 7;

int N;
int A[MAXN];

void input()
{
    read(N);
    for (int i = 1; i <= 2 * N - 1; ++i) {
        read(A[i]);
    }
}

void solve()
{
    std::sort(A + 1, A + 2 * N);

    static int dp[MAXN][MAXN][MAXN];

    dp[N-1][1][1] = 1;
    for (int i = N - 1; i >= 1; --i) {
        for (int j = 1; j <= 2 * N - 1; ++j) {
            for (int k = 1; k <= j; ++k) {
                if (!dp[i][j][k])
                    continue;
                int j0 = j + (A[i] != A[i+1]) + (A[2*N-i] != A[2*N-i-1]);
                int k0 = k + (A[i] != A[i+1]);
                for (int l = 1; l < k0; ++l) {
                    (dp[i-1][j0-(k0-l-1)][l] += dp[i][j][k]) %= MOD;
                }
                (dp[i-1][j0][k0] += dp[i][j][k]) %= MOD;
                for (int l = k0 + 1; l <= j0; ++l) {
                    (dp[i-1][j0-(l-k0-1)][k0+1] += dp[i][j][k]) %= MOD;
                }
            }
        }
    }

    int ans = 0;
    for (int j = 1; j <= 2 * N - 1; ++j) {
        for (int k = 1; k <= j; ++k) {
            (ans += dp[0][j][k]) %= MOD;
        }
    }

    printf("%d\n", ans);
}

int main()
{
#ifdef __DEBUG
    freopen("F.in", "r", stdin);
    freopen("F.out", "w", stdout);
#endif

    input();
    solve();

    return 0;
}

// 绿树村边合,青山郭外斜。
//     -- 孟浩然《过故人庄》

Submission Info

Submission Time
Task F - Prefix Median
User Ivlleiooq
Language C++14 (GCC 5.4.1)
Score 2000
Code Size 3523 Byte
Status AC
Exec Time 14 ms
Memory 3456 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 2000 / 2000
Status
AC × 3
AC × 54
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
All 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt
Case Name Status Exec Time Memory
00_example_01.txt AC 1 ms 256 KB
00_example_02.txt AC 1 ms 256 KB
00_example_03.txt AC 1 ms 384 KB
01.txt AC 14 ms 3456 KB
02.txt AC 11 ms 1280 KB
03.txt AC 3 ms 640 KB
04.txt AC 2 ms 512 KB
05.txt AC 2 ms 384 KB
06.txt AC 6 ms 896 KB
07.txt AC 14 ms 3456 KB
08.txt AC 2 ms 384 KB
09.txt AC 14 ms 3456 KB
10.txt AC 1 ms 256 KB
11.txt AC 1 ms 384 KB
12.txt AC 1 ms 384 KB
13.txt AC 5 ms 896 KB
14.txt AC 7 ms 1024 KB
15.txt AC 1 ms 256 KB
16.txt AC 6 ms 3072 KB
17.txt AC 1 ms 256 KB
18.txt AC 1 ms 256 KB
19.txt AC 1 ms 256 KB
20.txt AC 1 ms 384 KB
21.txt AC 1 ms 384 KB
22.txt AC 1 ms 256 KB
23.txt AC 2 ms 512 KB
24.txt AC 1 ms 384 KB
25.txt AC 2 ms 512 KB
26.txt AC 2 ms 640 KB
27.txt AC 1 ms 384 KB
28.txt AC 5 ms 1024 KB
29.txt AC 1 ms 384 KB
30.txt AC 2 ms 640 KB
31.txt AC 1 ms 256 KB
32.txt AC 2 ms 512 KB
33.txt AC 1 ms 256 KB
34.txt AC 2 ms 512 KB
35.txt AC 3 ms 896 KB
36.txt AC 1 ms 256 KB
37.txt AC 4 ms 1024 KB
38.txt AC 2 ms 512 KB
39.txt AC 2 ms 512 KB
40.txt AC 1 ms 384 KB
41.txt AC 3 ms 768 KB
42.txt AC 6 ms 3072 KB
43.txt AC 1 ms 384 KB
44.txt AC 7 ms 3200 KB
45.txt AC 1 ms 256 KB
46.txt AC 1 ms 256 KB
47.txt AC 1 ms 384 KB
48.txt AC 3 ms 640 KB
49.txt AC 4 ms 896 KB
50.txt AC 1 ms 256 KB
51.txt AC 2 ms 2432 KB