Submission #24900

#TimeUsernameProblemLanguageResultExecution timeMemory
24900dotorya마스코트 (JOI13_mascots)C++14
100 / 100
173 ms74720 KiB
#include <stdio.h> #include <algorithm> #include <assert.h> #include <bitset> #include <cmath> #include <complex> #include <deque> #include <functional> #include <iostream> #include <limits.h> #include <map> #include <math.h> #include <queue> #include <set> #include <stdlib.h> #include <string.h> #include <string> #include <time.h> #include <unordered_map> #include <unordered_set> #include <vector> #pragma warning(disable:4996) #pragma comment(linker, "/STACK:336777216") using namespace std; #define mp make_pair #define Fi first #define Se second #define pb(x) push_back(x) #define szz(x) ((int)(x).size()) #define rep(i, n) for(int i=0;i<n;i++) #define all(x) (x).begin(), (x).end() #define ldb ldouble typedef tuple<int, int, int> t3; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair <ll, int> pli; typedef pair <db, db> pdd; int IT_MAX = 1 << 19; const ll MOD = 1000000007; const int INF = 0x3f3f3f3f; const ll LL_INF = 0x3f3f3f3f3f3f3f3f; const db PI = acos(-1); const db ERR = 1E-11; ll mul_inv(ll a, ll b = MOD) { ll t1 = a, t2 = b, t3; ll v1 = 1, v2 = 0, v3; while (t2 != 1) { ll x = t1 / t2; t3 = t1 - x*t2; v3 = v1 - x*v2; t1 = t2, t2 = t3; v1 = v2, v2 = v3; } return (v2 + b) % b; } ll F[3050]; ll dp[3050][3050]; ll Comb(ll a, ll b) { ll rv = F[a]; rv = rv * mul_inv(F[b]) % MOD; rv = rv * mul_inv(F[a - b]) % MOD; return rv; } int main() { int R, C, N, i, j; F[0] = 1; for (i = 1; i <= 3000; i++) F[i] = F[i - 1] * i % MOD; scanf("%d %d %d", &R, &C, &N); int sx = INF, ex = -INF, sy = INF, ey = -INF; for (i = 1; i <= N; i++) { int t1, t2; scanf("%d %d", &t1, &t2); sx = min(sx, t1); ex = max(ex, t1); sy = min(sy, t2); ey = max(ey, t2); } dp[R][C] = 1; for (i = R; i >= 1; i--) { for (j = C; j >= 1; j--) { if (i != R) dp[i][j] = (dp[i][j] + dp[i + 1][j] * F[j]) % MOD; if (j != C) dp[i][j] = (dp[i][j] + dp[i][j + 1] * F[i]) % MOD; } } ll v = 1; for (i = 1; i <= (ex - sx + 1) * (ey - sy + 1) - N; i++) v = v*i%MOD; v = v * Comb(R - (ex - sx + 1), sx - 1) % MOD; v = v * Comb(C - (ey - sy + 1), sy - 1) % MOD; v = v * dp[ex - sx + 1][ey - sy + 1] % MOD; return !printf("%lld\n", v); }

Compilation message (stderr)

mascots.cpp:23:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable:4996)  
 ^
mascots.cpp:24:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/STACK:336777216")  
 ^
mascots.cpp: In function 'int main()':
mascots.cpp:79:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &R, &C, &N);
                               ^
mascots.cpp:84:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &t1, &t2);
                           ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...