제출 #75754

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
75754		cubecube1000	마스코트 (JOI13_mascots)	C++14	100 / 100	260 ms	135796 KiB

mascots

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
const ll MAX=3005;
const ll INFint=0x3f3f3f3f;
const ll INFLL=0x3f3f3f3f3f3f3f;
const ll MOD=1e9+7;
ll xmin=MAX,xmax=0,ymin=MAX,ymax=0,ans=1,xlen,ylen;
ll dp[MAX][MAX],dpv[MAX][MAX];
ll fact[MAX],finv[MAX],r,c,n;
ll power(ll x,ll y){
    if(y==0) return 1;
    ll t=power(x,y/2);
    if(y%2) return t*t%MOD*x%MOD;
    return t*t%MOD;
}
ll comb(ll x,ll y){
    if(y>x||y<0) return 0;
    return fact[x]*finv[x-y]%MOD*finv[y]%MOD;
}
ll build_dp(ll x,ll y){
    if(x<xlen) return 0;
    if(y<ylen) return 0;
    if(x==xlen&&y==ylen) return 1;
    if(dpv[x][y]==0){
        dpv[x][y]=1;
        dp[x][y]=(build_dp(x-1,y)*fact[y]+build_dp(x,y-1)*fact[x])%MOD;
    }
    return dp[x][y];
}
int main(){
    scanf("%lld%lld",&r,&c);
    scanf("%lld",&n);
    fact[0]=1;
    for(ll i=1;i<=max(r,c);i++) fact[i]=i*fact[i-1]%MOD;
    for(ll i=0;i<=max(r,c);i++) finv[i]=power(fact[i],MOD-2);
    for(ll i=0;i<n;i++){
        ll t1,t2;
        scanf("%lld%lld",&t1,&t2);
        xmin=min(xmin,t1),xmax=max(xmax,t1);
        ymin=min(ymin,t2),ymax=max(ymax,t2);
    }
    xlen=xmax-xmin+1, ylen=ymax-ymin+1;
    for(ll i=1;i<=xlen*ylen-n;i++) ans=(ans*i)%MOD;
    ans=(ans*build_dp(r,c))%MOD, ans=ans*comb(r-xlen,xmin-1)%MOD*comb(c-ylen,ymin-1)%MOD;
    printf("%lld\n",ans);
}

컴파일 시 표준 에러 (stderr) 메시지

mascots.cpp: In function 'int main()':
mascots.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld",&r,&c);
     ~~~~~^~~~~~~~~~~~~~~~~~
mascots.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&n);
     ~~~~~^~~~~~~~~~~
mascots.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld",&t1,&t2);
         ~~~~~^~~~~~~~~~~~~~~~~~~~

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