Submission #34995

#TimeUsernameProblemLanguageResultExecution timeMemory
34995nickyrio마스코트 (JOI13_mascots)C++14
40 / 100
3 ms142168 KiB
#include <bits/stdc++.h> #define FOR(i, a, b) for (int i = a; i<=b ; i++) #define FORD(i, a, b) for (int i = a; i>=b; i--) #define REP(i, a) for (int i = 0; i<a; i++) #define N 3030 #define pp pair<int, int> #define IO cin.tie(NULL);cout.tie(NULL); #define bit(S, i) ((S >> i) & 1) template<typename T> inline void read(T &x) { char c; bool neg = false; while (!isdigit(c = getchar()) && c != '-'); x = 0; if (c == '-') { neg = true; c = getchar(); } do { x = x * 10 + c - '0'; } while (isdigit(c = getchar())); if (neg) x = -x; } template<typename T> inline void write(T x) { if (x < 0) { putchar('-'); write(-x);return; } if (x < 10) { putchar(char(x + 48)); } else { write(x/10); putchar(char(48 + x%10)); } } template<typename T> inline void writeln(T x) { write(x); putchar('\n'); } using namespace std; const long long MOD = 1e9 + 7; int n, m, u, v, p, L, R, D, U; bool fr[N][N]; long long gt[N * N], need, dp[51][51][51][51]; bool used[51][51][51][51]; long long cal(int x1, int y1, int x2, int y2) { if (x1 == U && y1 == L && x2 == D && y2 == R) return need; if (used[x1][y1][x2][y2]) return dp[x1][y1][x2][y2]; used[x1][y1][x2][y2] = true; long long res = 0; if (y2 > y1 && y2 > R) res = (res + cal(x1, y1, x2, y2 - 1) * gt[x2 - x1 + 1] % MOD) % MOD; if (y2 > y1 && y1 < L) res = (res + cal(x1, y1 + 1, x2, y2) * gt[x2 - x1 + 1] % MOD) % MOD; if (x2 > x1 && x2 > D) res = (res + cal(x1, y1, x2 - 1, y2) * gt[y2 - y1 + 1] % MOD) % MOD; if (x2 > x1 && x1 < U) res = (res + cal(x1 + 1, y1, x2, y2) * gt[y2 - y1 + 1] % MOD) % MOD; dp[x1][y1][x2][y2] = res; return res; } int main() { IO; read(m);read(n); L = 1e9, R = -1e9, U = 1e9, D = -1e9; FOR(i, 1, m) FOR(j, 1, n) fr[i][j] = true; read(p); gt[0] = 1; FOR(i, 1, m * n) gt[i] = gt[i - 1] * 1ll * i % MOD; REP(i, p) { read(u);read(v); fr[u][v] = false; L = min(L, v); R = max(R, v); U = min(U, u); D = max(D, u); } need = gt[(D - U + 1) * (R - L + 1) - p]; writeln(cal(1, 1, m, n)); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...