Submission #43075

#	Time	Username	Problem	Language	Result	Execution time	Memory
43075		smu201111192	마스코트 (JOI13_mascots)	C++14	0 / 100	116 ms	141812 KiB

mascots

#include <iostream>
#include <cstdio>
#include <cassert>
#include <bitset>
#include <string>
#include <sstream>
#include <algorithm>
#include <set>
#include <numeric>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <queue>
#include <numeric>
#include <iomanip>
#define ll long long
using namespace std;
const int MAXN = 3005;
int r,c,n,yy,xx;
int mny,mxy,mnx,mxx;
long long fact[MAXN],dp[MAXN][MAXN],bino[MAXN][MAXN];
const long long mod = 1000000007;
void mul(long long &a,long long b){
    a = (a*b) % mod;
}
long long go(int a,int b){
    long long &ret = dp[a][b];
    if(ret != -1) return ret;
    if(a == r && b == c)return ret = 1;
    ret = 1;
    if(a < r){
        mul(ret,go(a+1,b));
        mul(ret,fact[b]);
    }
    if(b < c){
        mul(ret,go(a,b+1));
        mul(ret,fact[a]);
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> r >> c >> n;
    mny = mnx = 2e9;
    mxy = mxx = -2e9;
    for(int i = 0; i <= 3000; i++){
        bino[i][0] = 1;
        for(int j = 1; j <= 3000; j++){
            bino[i][j] = bino[i-1][j-1] + bino[i-1][j];
            bino[i][j] %= mod;
        }
    }
    for(int i = 1; i <= n; i++){
        cin >> yy >> xx;
        mny = min(mny,yy);
        mxy = max(mxy,yy);
        mnx = min(mnx,xx);
        mxx = max(mxx,xx);
    }
    long long tot = (mxy - mny + 1) * (mxx - mnx + 1) - n;
    fact[0] = 1;
    for(int i = 1; i <= 3000; i++) {fact[i] = fact[i-1] * i; fact[i] %= mod;}
    memset(dp,-1,sizeof(dp));
    long long ans = go(mxy-mny+1,mxx-mnx+1);
    mul(ans,fact[tot]);
    mul(ans,bino[mxy-mny+1][mny-1]);
    mul(ans,bino[c-(mxx-mnx+1)][mnx-1]);
    cout<<ans;
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60