oj.uz

Submission #43080

# Submission time Handle Problem Language Result Execution time Memory
43080 2018-03-08T20:45:53 Z smu201111192 마스코트 (JOI13_mascots) C++14
100 / 100
 320 ms 188652 KB 
#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*MAXN],dp[MAXN][MAXN];
long long bino[MAXN][MAXN];
const long long mod = 1000000007;
void mul(long long &a,int 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 = 0;
    if(a < r){
        ret += go(a+1,b) * fact[b];
        ret %= mod;
    }
    if(b < c){
        ret += go(a,b+1) * fact[a];
        ret %= mod;
    }
    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 <= i; 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 < MAXN*MAXN; 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[r-(mxy-mny+1)][mny-1]);
    mul(ans,bino[c-(mxx-mnx+1)][mnx-1]);
    cout<<ans;
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 187996 KB Output is correct
2 Correct 209 ms 188228 KB Output is correct
3 Correct 189 ms 188228 KB Output is correct
4 Correct 190 ms 188228 KB Output is correct
5 Correct 192 ms 188228 KB Output is correct
6 Correct 195 ms 188252 KB Output is correct
7 Correct 194 ms 188252 KB Output is correct
8 Correct 190 ms 188336 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 188336 KB Output is correct
2 Correct 186 ms 188336 KB Output is correct
3 Correct 188 ms 188352 KB Output is correct
4 Correct 187 ms 188352 KB Output is correct
5 Correct 186 ms 188352 KB Output is correct
6 Correct 194 ms 188352 KB Output is correct
7 Correct 190 ms 188352 KB Output is correct
8 Correct 196 ms 188352 KB Output is correct
9 Correct 188 ms 188352 KB Output is correct
10 Correct 188 ms 188352 KB Output is correct
11 Correct 190 ms 188352 KB Output is correct
12 Correct 189 ms 188352 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 188352 KB Output is correct
2 Correct 187 ms 188352 KB Output is correct
3 Correct 196 ms 188352 KB Output is correct
4 Correct 204 ms 188396 KB Output is correct
5 Correct 202 ms 188396 KB Output is correct
6 Correct 216 ms 188396 KB Output is correct
7 Correct 192 ms 188396 KB Output is correct
8 Correct 194 ms 188396 KB Output is correct
9 Correct 205 ms 188396 KB Output is correct
10 Correct 304 ms 188652 KB Output is correct
11 Correct 264 ms 188652 KB Output is correct
12 Correct 219 ms 188652 KB Output is correct
13 Correct 192 ms 188652 KB Output is correct
14 Correct 192 ms 188652 KB Output is correct
15 Correct 315 ms 188652 KB Output is correct
16 Correct 274 ms 188652 KB Output is correct
17 Correct 204 ms 188652 KB Output is correct
18 Correct 320 ms 188652 KB Output is correct