Submission #5181761


Source Code Expand

Copy
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 200005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 +c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
const int MOD = 1000000007;
int N;
int dp[55][105][105];
int a[105];
int inc(int a,int b) {
    return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a,int b) {
    return 1LL * a * b % MOD;
}
void update(int &x,int y) {
    x = inc(x,y);
}
void Solve() {
    read(N);
    for(int i = 1 ; i <= 2 * N - 1 ; ++i) read(a[i]);
    sort(a + 1,a + 2 * N);
    dp[1][1][1] = 1;
    for(int i = 1 ; i < N ; ++i) {
	for(int j = 1 ; j <= 2 * N - 1 ; ++j) {
	    for(int h = 1 ; h <= j ; ++h) {
		int tj = j,th = h;
		if(a[N + i] != a[N + i - 1]) ++tj;
		if(a[N - i] != a[N - i + 1]) ++tj,++th;
		for(int k = 1 ; k <= tj ; ++k) {
		    if(k < th)
			update(dp[i + 1][k + tj - th + 1][k],dp[i][j][h]);
		    else if(k > th)
			update(dp[i + 1][th + tj - k + 1][th + 1],dp[i][j][h]);
		    else if(k == th) 
			update(dp[i + 1][tj][th],dp[i][j][h]);
		}
	    }
	}
    }
    int ans = 0;
    for(int j = 1 ; j <= 2 * N - 1 ; ++j) {
	for(int h = 1 ; h <= j ; ++h) {
	    update(ans,dp[N][j][h]);
	}
    }
    out(ans);enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
}

Submission Info

Submission Time
Task F - Prefix Median
User sigongzi
Language C++14 (GCC 5.4.1)
Score 2000
Code Size 1902 Byte
Status
Exec Time 44 ms
Memory 2304 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
All 2000 / 2000 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 1 ms 256 KB
00_example_02.txt 1 ms 256 KB
00_example_03.txt 2 ms 512 KB
01.txt 44 ms 2304 KB
02.txt 32 ms 2176 KB
03.txt 7 ms 1024 KB
04.txt 3 ms 768 KB
05.txt 2 ms 640 KB
06.txt 16 ms 1536 KB
07.txt 44 ms 2304 KB
08.txt 2 ms 640 KB
09.txt 44 ms 2304 KB
10.txt 1 ms 256 KB
11.txt 1 ms 384 KB
12.txt 2 ms 512 KB
13.txt 12 ms 1408 KB
14.txt 21 ms 1792 KB
15.txt 1 ms 256 KB
16.txt 44 ms 2304 KB
17.txt 1 ms 384 KB
18.txt 1 ms 256 KB
19.txt 1 ms 256 KB
20.txt 2 ms 384 KB
21.txt 2 ms 384 KB
22.txt 1 ms 256 KB
23.txt 6 ms 1024 KB
24.txt 2 ms 512 KB
25.txt 5 ms 896 KB
26.txt 7 ms 1024 KB
27.txt 2 ms 512 KB
28.txt 37 ms 2304 KB
29.txt 3 ms 640 KB
30.txt 7 ms 1024 KB
31.txt 1 ms 256 KB
32.txt 6 ms 1024 KB
33.txt 1 ms 256 KB
34.txt 5 ms 896 KB
35.txt 32 ms 2048 KB
36.txt 1 ms 256 KB
37.txt 32 ms 2176 KB
38.txt 6 ms 1024 KB
39.txt 3 ms 768 KB
40.txt 2 ms 640 KB
41.txt 16 ms 1536 KB
42.txt 44 ms 2304 KB
43.txt 2 ms 640 KB
44.txt 44 ms 2304 KB
45.txt 1 ms 256 KB
46.txt 1 ms 384 KB
47.txt 2 ms 512 KB
48.txt 12 ms 1408 KB
49.txt 21 ms 1792 KB
50.txt 1 ms 256 KB
51.txt 43 ms 2304 KB