oj.uz

답안 #448224

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
448224 2021-07-29T10:37:39 Z cpp219 마스코트 (JOI13_mascots) C++14
100 / 100
 360 ms 213276 KB 
#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

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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 211968 KB Output is correct
2 Correct 157 ms 212124 KB Output is correct
3 Correct 156 ms 212036 KB Output is correct
4 Correct 159 ms 212172 KB Output is correct
5 Correct 155 ms 212036 KB Output is correct
6 Correct 159 ms 212100 KB Output is correct
7 Correct 164 ms 212124 KB Output is correct
8 Correct 159 ms 212012 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 212080 KB Output is correct
2 Correct 159 ms 211984 KB Output is correct
3 Correct 165 ms 212048 KB Output is correct
4 Correct 157 ms 211992 KB Output is correct
5 Correct 170 ms 212068 KB Output is correct
6 Correct 165 ms 212016 KB Output is correct
7 Correct 161 ms 211968 KB Output is correct
8 Correct 173 ms 211956 KB Output is correct
9 Correct 161 ms 211984 KB Output is correct
10 Correct 160 ms 212036 KB Output is correct
11 Correct 173 ms 212060 KB Output is correct
12 Correct 162 ms 211964 KB Output is correct

Subtask #3
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 162 ms 211980 KB Output is correct
2 Correct 161 ms 212016 KB Output is correct
3 Correct 182 ms 212052 KB Output is correct
4 Correct 175 ms 212040 KB Output is correct
5 Correct 178 ms 212184 KB Output is correct
6 Correct 199 ms 212932 KB Output is correct
7 Correct 166 ms 212048 KB Output is correct
8 Correct 181 ms 212312 KB Output is correct
9 Correct 173 ms 212724 KB Output is correct
10 Correct 332 ms 212256 KB Output is correct
11 Correct 253 ms 212356 KB Output is correct
12 Correct 182 ms 212640 KB Output is correct
13 Correct 169 ms 212036 KB Output is correct
14 Correct 165 ms 212064 KB Output is correct
15 Correct 360 ms 213104 KB Output is correct
16 Correct 300 ms 212324 KB Output is correct
17 Correct 175 ms 212544 KB Output is correct
18 Correct 357 ms 213276 KB Output is correct