oj.uz

Submission #43049

# Submission time Handle Problem Language Result Execution time Memory
43049 2018-03-08T11:04:13 Z ffresh 마스코트 (JOI13_mascots) C++14
40 / 100
 128 ms 142360 KB 
#include <bits/stdc++.h>

using namespace std;

const int N =3005,mod = 1e9+7;


#define ll long long

ll per[N];

ll mypow(ll x,ll c){
	ll ret=1;
	while(c){
		if(c&1)
			ret= (ret*x)%mod;

		x = (x*x)%mod;
		c>>=1;
	}
	return ret;
}

ll dp[N][N];


ll solve(int x,int y,int lx,int ly,int a,int b){

	if(x==lx && ly==y)return 1;

	ll &ret= dp[x][y];

	if(ret!=-1)return ret;

	ret = 0;

	if(y<ly){
		ll temp = a+x;
		temp = per[temp];
		ret = (ret + temp*solve(x,y+1,lx,ly,a,b))%mod;
	}
	if(x<lx){
		ll temp = b+y;

		temp = per[temp];
		ret= (ret + temp*solve(x+1,y,lx,ly,a,b))%mod;
	}
	return ret;
}

ll combi(int n,int c){
	ll ret= per[n];
	ret = (ret *mypow(per[c],mod-2))%mod;
	ret = (ret *mypow(per[n-c],mod-2))%mod;
	return ret;
}
int main(){
	//freopen("input.txt","r",stdin);
	per[0]= 1;
	for(int i=1;i<N;++i)per[i]=(per[i-1]*i)%mod;
	memset(dp,-1,sizeof(dp));
	int dx=N,dy =N,ux=0,uy = 0;
	int r,c,n;
	cin>>r>>c>>n;
	for(int i=0;i<n;++i){
		int u,v;
		cin>>u>>v;
		dx= min(dx,u),dy= min(dy,v);
		ux= max(ux,u),uy= max(uy,v);
	}
	int a = ux-dx+1;
	int b= uy-dy+1;
	int tot = a*b - n;
	
	ll ret = per[tot];

	ret = (ret * combi(r-a,dx-1))%mod;
	ret = (ret*combi(c-b,dy-1))%mod;

	ret= (ret * solve(0,0,r-a,c-b,a,b))%mod;
	cout<<ret<<endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 71032 KB Output is correct
2 Correct 55 ms 71140 KB Output is correct
3 Correct 55 ms 71248 KB Output is correct
4 Correct 53 ms 71248 KB Output is correct
5 Correct 54 ms 71248 KB Output is correct
6 Correct 53 ms 71400 KB Output is correct
7 Correct 54 ms 71400 KB Output is correct
8 Correct 53 ms 71416 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 71416 KB Output is correct
2 Correct 55 ms 71416 KB Output is correct
3 Correct 57 ms 71416 KB Output is correct
4 Correct 53 ms 71416 KB Output is correct
5 Correct 57 ms 71416 KB Output is correct
6 Correct 54 ms 71552 KB Output is correct
7 Correct 54 ms 71552 KB Output is correct
8 Correct 58 ms 71552 KB Output is correct
9 Correct 68 ms 71552 KB Output is correct
10 Correct 55 ms 71552 KB Output is correct
11 Correct 53 ms 71552 KB Output is correct
12 Correct 55 ms 71552 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 71552 KB Output is correct
2 Runtime error 128 ms 142360 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -