oj.uz

Submission #43053

# Submission time Handle Problem Language Result Execution time Memory
43053 2018-03-08T11:18:42 Z ffresh 마스코트 (JOI13_mascots) C++14
40 / 100
 4 ms 752 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];



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;
	
	int dx=N,dy =N,ux=0,uy = 0;
	int r,c,n;
	cin>>r>>c>>n;
	assert(r<N && 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;
	dp[0][0]=1;
	int x,y;
	int lx = r-a, ly = c-b;

	for(x=0;x<=lx;++x){
		for(y=0;y<=ly;++y){
			if(y<ly){
				ll temp = a+x;
				temp = per[temp];
				temp = (temp*dp[x][y])%mod;
				dp[x][y+1]= (dp[x][y+1]+ temp)%mod;
			}
			if(x<lx){
				ll temp = b+y;
				temp = per[temp];
				temp = (temp*dp[x][y])%mod;
				dp[x+1][y]= (dp[x+1][y]+ temp)%mod;
			}
		}
	}
	ret = (ret*dp[lx][ly])%mod;
	cout<<ret<<endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 536 KB Output is correct
4 Correct 1 ms 536 KB Output is correct
5 Correct 2 ms 536 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 2 ms 592 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 592 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 732 KB Output is correct
8 Correct 2 ms 732 KB Output is correct
9 Correct 2 ms 748 KB Output is correct
10 Correct 2 ms 748 KB Output is correct
11 Correct 2 ms 748 KB Output is correct
12 Correct 2 ms 748 KB Output is correct

Subtask #3
0 / 60.0

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