Submission #1190523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190523		vnedu	마스코트 (JOI13_mascots)	C++17	100 / 100	254 ms	71256 KiB

mascots

#include<bits/stdc++.h>
using namespace std;
//typedef long long ll;

template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }

#define fi first
#define se second

#define pb push_back
#define ii pair<int, int>

#define all(x) x.begin(), x.end()

#define TASK "nonsense"

/// end of template ///

const int N = 3e3 + 10;
const int mod = 1e9 + 7;
int r,c,n,f[N],C[N][N];
void addSelf(int &x, int val)
{
    x+=val;
    if(x>=mod) x-=mod;
    else if(x<0) x+=mod;
}
void init()
{
    f[0]=1;
    for(int i=1;i<N;++i) f[i]=f[i-1]*1LL*i%mod;
    for(int i=0;i<N;++i) C[i][0]=1;
    for(int i=1;i<N;++i) for(int j=1;j<N;++j)
    {
        int &cur=C[i][j];
        cur=C[i-1][j]+C[i-1][j-1];
        if(cur>=mod) cur-=mod;
    }
}
int lb=INT_MAX,lt=INT_MIN,ll=INT_MAX,lr=INT_MIN,d1,d2,k,dp[N][N];
void solve()
{
    init();
    cin>>r>>c>>n;
    for(int tri=1;tri<=n;++tri)
    {
        int x,y; cin>>x>>y;
        minimize(lb,x);
        maximize(lt,x);
        minimize(ll,y);
        maximize(lr,y);
    }
//    cout<<C[2][1];
//    return;
    d1=lt-lb+1;
    d2=lr-ll+1;
    k=lb-1+r-lt+ll-1+c-lr;
    int ans=1;
    for(int i=1;i<=d2*d1-n;++i) ans=ans*1LL*i%mod;
    dp[0][0]=1;
    for(int sum=0;sum<k;++sum) for(int x1=0;x1<=sum;++x1)
    {
        int x2=sum-x1;
//        cout<<x1<<' '<<x2<<' '<<dp[x1][x2]<<'\n';
        addSelf(dp[x1][x2+1],dp[x1][x2]*1LL*f[d1+x1]%mod);
        addSelf(dp[x1+1][x2],dp[x1][x2]*1LL*f[d2+x2]%mod);
    }
    int x1=lb-1+r-lt;
    int x2=ll-1+c-lr;
//    cout<<x1<<' '<<lb-1<<' '<<x2<<' '<<ll-1<<'\n';
//    cout<<dp[x1][x2]<<'\n';
//    cout<<dp[x1][x2]*1LL*C[x1][lb-1]%mod*1LL*C[x2][ll-1]%mod<<'\n';
//    cout<<ans<<'\n';
    ans=ans*1LL*(dp[x1][x2]*1LL*C[x1][lb-1]%mod*1LL*C[x2][ll-1]%mod)%mod;
//    cout<<k<<'\n';
//    return;
    cout<<ans;
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);

    int testcase=1;
//    cin>>testcase;

    while (testcase--)
        solve();

    return 0;
}

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