Submission #2198372


Source Code Expand

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

typedef long long ll;
const int MOD = 1000000007;
const int N = 404;

int n, m, ans;
int a[N], b[N];
int f[N][N][N], g[N][N][N];
int cnt[N];
int dp[N][N][N];
int ok[N][N];

inline void add(int &x, int a) {
	x = (x + a > MOD) ? x + a - MOD : x + a;
}
inline void sub(int &x, int a) {
	x = (x < a) ? x - a + MOD : x - a;
}

int main(void) {
	scanf("%d", &n); m = n / 3;
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++) scanf("%d", &b[i]);

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			ok[i][j] = 1;
			for (int k = 1; k <= i; k++)
				if (a[k] == b[j]) ok[i][j] = 0;
			for (int k = 1; k <= j; k++)
				if (b[k] == a[i]) ok[i][j] = 0;
		}
	
	int size;
	for (int t = 1; t <= m; t++) {
		size = 0;
		for (int i = 1; i <= n; i++) cnt[i] = 0;
		for (int i = 1; i <= n; i++) {
			if (!cnt[a[i]]) ++size;
			++cnt[a[i]];
			for (int j = 1; j <= n; j++) {
				if (!cnt[b[j]]) ++size;
				++cnt[b[j]];
				if (ok[i][j])
					f[t][i][j] = n - 3 * (m - t) - size;
			}
			for (int j = 1; j <= n; j++) {
				--cnt[b[j]];
				if (!cnt[b[j]]) --size;
			}
		}
	}

	g[0][0][0] = 1;
	for (int i = 0; i <= m; i++)
		for (int j = 0; j <= m; j++)
			for (int k = max(i, j); k <= m; k++)
				if (g[i][j][k]) {
					if (i < m) add(g[i + 1][j][k], (ll)(k - i) * g[i][j][k] % MOD);
					if (j < m) add(g[i][j + 1][k], (ll)(k - j) * g[i][j][k] % MOD);
					if (k < m) add(g[i][j][k + 1], g[i][j][k]);
				}

	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= n; j++)
			dp[0][i][j] = 1;
	for (int t = 1; t <= m; t++) {
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++) {
				dp[t][i][j] = 0;
				if (!ok[i][j]) continue;
				add(dp[t][i][j], (ll)dp[t - 1][i - 1][j - 1] * f[t][i][j] % MOD);
			}
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				add(dp[t][i][j], dp[t][i - 1][j]);
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				add(dp[t][i][j], dp[t][i][j - 1]);
	}
	
	ans = (ll)dp[m][n][n] * g[m][m][m] % MOD;
	cout << ans << endl;
	return 0;
}
 

Submission Info

Submission Time
Task F - Three Gluttons
User Vectorxj
Language C++14 (GCC 5.4.1)
Score 1800
Code Size 2162 Byte
Status AC
Exec Time 283 ms
Memory 260352 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:23:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n); m = n / 3;
                 ^
./Main.cpp:24:49: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
                                                 ^
./Main.cpp:25:49: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
                                                 ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1800 / 1800
Status
AC × 5
AC × 37
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt
Case Name Status Exec Time Memory
0_00.txt AC 2 ms 4352 KB
0_01.txt AC 2 ms 2304 KB
0_02.txt AC 2 ms 4352 KB
0_03.txt AC 2 ms 4352 KB
0_04.txt AC 3 ms 8448 KB
1_00.txt AC 238 ms 174336 KB
1_01.txt AC 263 ms 260352 KB
1_02.txt AC 264 ms 260352 KB
1_03.txt AC 266 ms 260352 KB
1_04.txt AC 265 ms 260352 KB
1_05.txt AC 267 ms 260352 KB
1_06.txt AC 267 ms 260352 KB
1_07.txt AC 277 ms 260352 KB
1_08.txt AC 276 ms 258304 KB
1_09.txt AC 276 ms 258304 KB
1_10.txt AC 271 ms 254208 KB
1_11.txt AC 271 ms 254208 KB
1_12.txt AC 260 ms 252032 KB
1_13.txt AC 282 ms 260352 KB
1_14.txt AC 277 ms 258304 KB
1_15.txt AC 283 ms 260352 KB
1_16.txt AC 273 ms 260352 KB
1_17.txt AC 273 ms 260352 KB
1_18.txt AC 268 ms 258304 KB
1_19.txt AC 267 ms 258304 KB
1_20.txt AC 262 ms 254208 KB
1_21.txt AC 274 ms 260352 KB
1_22.txt AC 273 ms 260352 KB
1_23.txt AC 273 ms 260352 KB
1_24.txt AC 275 ms 258304 KB
1_25.txt AC 281 ms 260352 KB
1_26.txt AC 265 ms 254080 KB
1_27.txt AC 275 ms 258304 KB
1_28.txt AC 275 ms 258304 KB
1_29.txt AC 281 ms 260352 KB
1_30.txt AC 269 ms 254208 KB
1_31.txt AC 264 ms 254080 KB