oj.uz

Submission #43052

# Submission time Handle Problem Language Result Execution time Memory
43052 2018-03-08T11:12:53 Z ffresh 마스코트 (JOI13_mascots) C++14
40 / 100
 66 ms 71400 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;
	if(r>=N ||  c>=N){
      
      cout<<"FUCKING MEMORY\n";
      assert(0);
    }
	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 30 ms 35708 KB Output is correct
2 Correct 28 ms 35804 KB Output is correct
3 Correct 27 ms 35804 KB Output is correct
4 Correct 27 ms 35836 KB Output is correct
5 Correct 29 ms 35884 KB Output is correct
6 Correct 28 ms 35980 KB Output is correct
7 Correct 28 ms 35980 KB Output is correct
8 Correct 28 ms 35980 KB Output is correct

Subtask #2
30.0 / 30.0

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

Subtask #3
0 / 60.0

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