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 |
|
|
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 |