oj.uz

Submission #43079

# Submission time Handle Problem Language Result Execution time Memory
43079 2018-03-08T20:41:20 Z smu201111192 마스코트 (JOI13_mascots) C++14
40 / 100
 191 ms 197596 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],dp[MAXN][MAXN];
int 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 <= 3000; 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 80 ms 98600 KB Output is correct
2 Correct 86 ms 98784 KB Output is correct
3 Correct 79 ms 98784 KB Output is correct
4 Correct 80 ms 98800 KB Output is correct
5 Correct 77 ms 98836 KB Output is correct
6 Correct 77 ms 98944 KB Output is correct
7 Correct 77 ms 98944 KB Output is correct
8 Correct 82 ms 98944 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 98960 KB Output is correct
2 Correct 77 ms 98960 KB Output is correct
3 Correct 77 ms 98960 KB Output is correct
4 Correct 78 ms 99016 KB Output is correct
5 Correct 83 ms 99016 KB Output is correct
6 Correct 91 ms 99016 KB Output is correct
7 Correct 77 ms 99016 KB Output is correct
8 Correct 77 ms 99016 KB Output is correct
9 Correct 79 ms 99052 KB Output is correct
10 Correct 80 ms 99052 KB Output is correct
11 Correct 81 ms 99052 KB Output is correct
12 Correct 78 ms 99052 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 99052 KB Output is correct
2 Runtime error 191 ms 197596 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -