oj.uz

Submission #43051

# Submission time Handle Problem Language Result Execution time Memory
43051 2018-03-08T11:11:37 Z ffresh 마스코트 (JOI13_mascots) C++14
40 / 100
 68 ms 71464 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;
}

int dp[N][N];


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

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

	int &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)%mod;
	}
	if(x<lx){
		ll temp = b+y;

		temp = per[temp];
		ret= (ret + (temp*solve(x+1,y,lx,ly,a,b) )%mod  )%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 28 ms 35704 KB Output is correct
2 Correct 28 ms 35708 KB Output is correct
3 Correct 29 ms 35740 KB Output is correct
4 Correct 28 ms 35744 KB Output is correct
5 Correct 28 ms 35916 KB Output is correct
6 Correct 28 ms 35916 KB Output is correct
7 Correct 29 ms 35916 KB Output is correct
8 Correct 29 ms 35916 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 35916 KB Output is correct
2 Correct 29 ms 35916 KB Output is correct
3 Correct 28 ms 35916 KB Output is correct
4 Correct 29 ms 35988 KB Output is correct
5 Correct 27 ms 35988 KB Output is correct
6 Correct 28 ms 35988 KB Output is correct
7 Correct 29 ms 35988 KB Output is correct
8 Correct 29 ms 35988 KB Output is correct
9 Correct 28 ms 35988 KB Output is correct
10 Correct 28 ms 36040 KB Output is correct
11 Correct 29 ms 36040 KB Output is correct
12 Correct 28 ms 36040 KB Output is correct

Subtask #3
0 / 60.0

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