Submission #448224

#	Time	Username	Problem	Language	Result	Execution time	Memory
448224		cpp219	마스코트 (JOI13_mascots)	C++14	100 / 100	360 ms	213276 KiB

mascots

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 3e3 + 3;
const ll mod = 1e9 + 7;

ll R,C,n,x,y,dp[N][N],c[N][N];
ll maxx,maxy,minx = mod,miny = mod;
ll fac[N*N],lim_ngang,lim_doc,pel;

ll g(ll k,ll n){
    if (k == 0) return 1;
    if (k > n) return 0;
    if (k == n) return 1;
    if (k == 1) return n;
    if (c[k][n] != -1) return c[k][n];
    return c[k][n] = (g(k,n - 1) + g(k - 1,n - 1))%mod;
}

ll f(ll cnt1,ll cnt2){
    if (cnt1 == R&&cnt2 == C) return 1;
    if (dp[cnt1][cnt2] != -1) return dp[cnt1][cnt2];
    ll ans = 0;
    if (cnt1 < R) ans = (ans + (f(cnt1 + 1,cnt2)*fac[cnt2])%mod)%mod;
    if (cnt2 < C) ans = (ans + (f(cnt1,cnt2 + 1)*fac[cnt1])%mod)%mod;
    return dp[cnt1][cnt2] = ans;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define task "tst"
    if (fopen(task".INP","r")){
        freopen(task".INP","r",stdin);
        //freopen(task".OUT","w",stdout);
    }
    cin>>R>>C>>n; memset(dp,-1,sizeof(dp)); memset(c,-1,sizeof(c));
    for (ll i = 1;i <= n;i++){
        cin>>x>>y;
        maxx = max(maxx,x); maxy = max(maxy,y);
        minx = min(minx,x); miny = min(miny,y);
    }
    fac[0] = 1;
    for (ll i = 1;i <= N*N;i++) fac[i] = (fac[i - 1]*i)%mod;
    ll doc = maxx - minx + 1,ngang = maxy - miny + 1;
    lim_ngang = C - ngang; lim_doc = R - doc;
    pel = (g(minx - 1,lim_doc)*g(miny - 1,lim_ngang))%mod; //cout<<doc<<" "<<ngang; return 0;
    pel = (fac[doc*ngang - n]*pel)%mod;
    cout<<(f(doc,ngang)*pel)%mod;
}

Compilation message (stderr)

mascots.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
mascots.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
mascots.cpp: In function 'int main()':
mascots.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
mascots.cpp:52:40: warning: iteration 9018008 invokes undefined behavior [-Waggressive-loop-optimizations]
   52 |     for (ll i = 1;i <= N*N;i++) fac[i] = (fac[i - 1]*i)%mod;
      |                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~
mascots.cpp:52:21: note: within this loop
   52 |     for (ll i = 1;i <= N*N;i++) fac[i] = (fac[i - 1]*i)%mod;
      |                   ~~^~~~~~

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