oj.uz

Submission #202930

# Submission time Handle Problem Language Result Execution time Memory
202930 2020-02-18T17:57:29 Z arnold518 마스코트 (JOI13_mascots) C++14
100 / 100
 257 ms 137440 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3000;
const ll MOD = 1e9+7;

int N, M, Q, X, Y;
int xl, xr, yl, yr;

ll fact[MAXN*MAXN+10], dp[MAXN+10][MAXN+10];

ll mypow(ll x, ll y)
{
	if(y==0) return 1;
	if(y%2) return mypow(x, y-1)*x%MOD;
	ll t=mypow(x, y/2);
	return t*t%MOD;
}

ll inv(ll x) { return mypow(x, MOD-2); }

ll comb(ll n, ll r) { return fact[n]*inv(fact[r])%MOD*inv(fact[n-r])%MOD; }

int main()
{
	int i, j;

	scanf("%d%d%d", &N, &M, &Q);
	yr=1; yl=N; xr=1; xl=M;
	for(i=1; i<=Q; i++)
	{
		int y, x;
		scanf("%d%d", &y, &x);
		yl=min(yl, y); yr=max(yr, y);
		xl=min(xl, x); xr=max(xr, x);
	}
	Y=N-(yr-yl+1);
	X=M-(xr-xl+1);

	fact[0]=1;
	for(i=1; i<=MAXN*MAXN; i++) fact[i]=fact[i-1]*i%MOD;

	for(i=0; i<=Y; i++) for(j=0; j<=X; j++)
	{
		if(i==0 && j==0) { dp[i][j]=1; continue; }
		if(i) dp[i][j]=(dp[i][j]+dp[i-1][j]*fact[M-X+j]%MOD)%MOD;
		if(j) dp[i][j]=(dp[i][j]+dp[i][j-1]*fact[N-Y+i]%MOD)%MOD;
	}
	dp[Y][X]=dp[Y][X]*comb(Y, yl-1)%MOD;
	dp[Y][X]=dp[Y][X]*comb(X, xl-1)%MOD;
	dp[Y][X]=dp[Y][X]*fact[(yr-yl+1)*(xr-xl+1)-Q]%MOD;
	printf("%lld\n", dp[Y][X]);
}

Compilation message

mascots.cpp: In function 'int main()':
mascots.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &M, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
mascots.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &y, &x);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 70776 KB Output is correct
2 Correct 87 ms 70780 KB Output is correct
3 Correct 104 ms 70812 KB Output is correct
4 Correct 87 ms 70776 KB Output is correct
5 Correct 88 ms 70776 KB Output is correct
6 Correct 89 ms 70776 KB Output is correct
7 Correct 87 ms 70776 KB Output is correct
8 Correct 111 ms 70740 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 70776 KB Output is correct
2 Correct 86 ms 70804 KB Output is correct
3 Correct 90 ms 70776 KB Output is correct
4 Correct 86 ms 70904 KB Output is correct
5 Correct 87 ms 70780 KB Output is correct
6 Correct 89 ms 70780 KB Output is correct
7 Correct 87 ms 70776 KB Output is correct
8 Correct 89 ms 70776 KB Output is correct
9 Correct 87 ms 71008 KB Output is correct
10 Correct 89 ms 70776 KB Output is correct
11 Correct 93 ms 70776 KB Output is correct
12 Correct 87 ms 70776 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 70776 KB Output is correct
2 Correct 95 ms 71288 KB Output is correct
3 Correct 101 ms 72228 KB Output is correct
4 Correct 108 ms 79888 KB Output is correct
5 Correct 110 ms 78560 KB Output is correct
6 Correct 123 ms 76720 KB Output is correct
7 Correct 91 ms 72312 KB Output is correct
8 Correct 90 ms 70776 KB Output is correct
9 Correct 106 ms 71428 KB Output is correct
10 Correct 234 ms 137080 KB Output is correct
11 Correct 185 ms 115480 KB Output is correct
12 Correct 111 ms 71416 KB Output is correct
13 Correct 93 ms 72800 KB Output is correct
14 Correct 91 ms 70776 KB Output is correct
15 Correct 253 ms 137440 KB Output is correct
16 Correct 198 ms 120544 KB Output is correct
17 Correct 113 ms 75768 KB Output is correct
18 Correct 257 ms 134648 KB Output is correct