Submission #5626145


Source Code Expand

Copy
#include <bits/stdc++.h>
#define mset(a, b) memset(a, b, sizeof(a))
#define mcpy(a, b) memcpy(a, b, sizeof(a))
#define rg register
using namespace std;
typedef long long LL;
const int N = 55;
const int MOD = 1e9 + 7;

template <typename T> inline void read(T &AKNOI) {
	T x = 0, flag = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-') flag = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	AKNOI = flag * x;
}

int n, nn, a[N<<1];
int dp[N][N<<1][N<<1];

inline void Inc(int &x, int y) {
	x += y; if (x >= MOD) x -= MOD;
}

void init() {
	read(n); nn = n*2-1;
	for (int i=1;i<=nn;++i) {
		read(a[i]);
	}
	sort(a+1, a+nn+1);
}

void solve() {
	dp[n][1][0] = 1;
	for (int i=n-1;i>=1;--i) {
		int fl = (a[i] != a[i+1]), fr = (a[nn-i+1] != a[nn-i]);
		for (int l=0;l<=nn;++l) {
			for (int r=0;r<=nn-l;++r) {
				int x = dp[i+1][l][r];
				if (!x) continue;
				for (int j=1;j<=l+fl;++j) {
					Inc(dp[i][l+fl-j+1][r+fr+(j>1)], x);
				}
				for (int j=1;j<=r+fr;++j) {
					Inc(dp[i][l+fl+1][r+fr-j], x);
				}
			}
		}
	}
	int ans = 0;
	for (int l=0;l<=nn;++l) {
		for (int r=0;r<=nn-l;++r) {
			Inc(ans, dp[1][l][r]);
		}
	}
	printf("%d\n", ans);
}

int main() {
	init();
	solve();
	return 0;
}

Submission Info

Submission Time
Task F - Prefix Median
User tyler178
Language C++14 (GCC 5.4.1)
Score 2000
Code Size 1327 Byte
Status
Exec Time 19 ms
Memory 1536 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 1 ms 384 KB
01.txt 19 ms 1536 KB
02.txt 14 ms 1280 KB
03.txt 3 ms 768 KB
04.txt 2 ms 512 KB
05.txt 2 ms 512 KB
06.txt 7 ms 1024 KB
07.txt 19 ms 1536 KB
08.txt 2 ms 512 KB
09.txt 19 ms 1536 KB
10.txt 1 ms 256 KB
11.txt 1 ms 384 KB
12.txt 1 ms 384 KB
13.txt 6 ms 896 KB
14.txt 10 ms 1152 KB
15.txt 1 ms 256 KB
16.txt 7 ms 1152 KB
17.txt 1 ms 384 KB
18.txt 1 ms 256 KB
19.txt 1 ms 256 KB
20.txt 1 ms 384 KB
21.txt 1 ms 384 KB
22.txt 1 ms 256 KB
23.txt 2 ms 512 KB
24.txt 1 ms 384 KB
25.txt 2 ms 512 KB
26.txt 2 ms 640 KB
27.txt 1 ms 384 KB
28.txt 7 ms 1152 KB
29.txt 2 ms 512 KB
30.txt 2 ms 640 KB
31.txt 1 ms 256 KB
32.txt 2 ms 640 KB
33.txt 1 ms 256 KB
34.txt 2 ms 512 KB
35.txt 4 ms 896 KB
36.txt 1 ms 256 KB
37.txt 6 ms 1024 KB
38.txt 2 ms 640 KB
39.txt 2 ms 512 KB
40.txt 1 ms 384 KB
41.txt 3 ms 768 KB
42.txt 8 ms 1152 KB
43.txt 1 ms 384 KB
44.txt 8 ms 1152 KB
45.txt 1 ms 256 KB
46.txt 1 ms 384 KB
47.txt 1 ms 384 KB
48.txt 3 ms 768 KB
49.txt 5 ms 896 KB
50.txt 1 ms 256 KB
51.txt 2 ms 512 KB