oj.uz

Submission #147110

# Submission time Handle Problem Language Result Execution time Memory
147110 2019-08-27T14:02:40 Z red1108 마스코트 (JOI13_mascots) C++17
40 / 100
 2000 ms 43432 KB 
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<vector>
#include<utility>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<ext/rope>
#include<unordered_set>
#include<unordered_map>
using namespace std;
using namespace __gnu_cxx;
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false);cin.tie(0)
#define fopen freopen("input.txt", "r", stdin)
#define pb push_back
#define enter "\n" 
#define space " "
#define pr2(a,b) cout<<(a)<<" "<<(b)<<endl
#define pr3(a,b,c) cout<<(a)<<" "<<(b)<<" "<<(c)<<endl
#define pr4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<endl
#define prec(a) cout<<fixed;cout.precision(a);
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
const ll INF = 1e18;
const int inf = 1e9;

int n, m,s=inf,e,hs=inf,he;
ll pac[9000010],mod=1000000007,ipac[9000010],dp[3010][3010],w,h;
ll mypow(ll a, ll b){
	ll ret=1;
	while(b){
		if(b&1) ret = ret*a%mod;
		a = a*a%mod;
		b>>=1;
	}
	return ret;
}
int main(){
	fastio;
	cin>>n>>m;
	int p;
	cin>>p;
	for(int i=1;i<=p;i++){
		int a, b;
		cin>>a>>b;
		hs=min(hs,a);
		he=max(he,a);
		s=min(s,b);
		e=max(e,b);
	}
	pac[0]=1;
	ipac[0]=1;
	for(int i=1;i<=n*m;i++){
		pac[i]=pac[i-1]*i%mod;
		ipac[i]=ipac[i-1]*mypow(i,mod-2)%mod;
	}
	w = e-s+1;
	h = he-hs+1;
	dp[h][w]=1;
	for(int i=h;i<=n;i++){
		for(int j=w;j<=m;j++){
			if(i==h&&j==w) continue;
			dp[i][j]=(dp[i-1][j]*pac[j]%mod+dp[i][j-1]*pac[i]%mod)%mod;
		}
	}
	ll ans = dp[n][m],ww=1,hh=1;
	ans = ans*pac[w*h-p]%mod;
	ww = pac[m-w]*ipac[s-1]%mod*ipac[m-e]%mod;
	hh = pac[n-h]*ipac[hs-1]%mod*ipac[n-he]%mod;
	ans = ans*ww%mod*hh%mod;
	cout<<ans;
}

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 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 424 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 380 KB Output is correct
9 Correct 4 ms 604 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 4 ms 504 KB Output is correct
12 Correct 3 ms 348 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1016 KB Output is correct
2 Correct 65 ms 2168 KB Output is correct
3 Correct 74 ms 3240 KB Output is correct
4 Correct 658 ms 21832 KB Output is correct
5 Correct 665 ms 20932 KB Output is correct
6 Correct 788 ms 21988 KB Output is correct
7 Correct 1288 ms 28828 KB Output is correct
8 Execution timed out 2057 ms 43432 KB Time limit exceeded
9 Halted 0 ms 0 KB -