oj.uz

Submission #43078

# Submission time Handle Problem Language Result Execution time Memory
43078 2018-03-08T20:39:58 Z smu201111192 마스코트 (JOI13_mascots) C++14
40 / 100
 232 ms 234832 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],bino[MAXN][MAXN];
const long long mod = 1000000007;
void mul(long long &a,long long 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 88 ms 117368 KB Output is correct
2 Correct 90 ms 117476 KB Output is correct
3 Correct 89 ms 117476 KB Output is correct
4 Correct 99 ms 117572 KB Output is correct
5 Correct 88 ms 117572 KB Output is correct
6 Correct 93 ms 117572 KB Output is correct
7 Correct 101 ms 117572 KB Output is correct
8 Correct 91 ms 117572 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 117676 KB Output is correct
2 Correct 93 ms 117676 KB Output is correct
3 Correct 88 ms 117676 KB Output is correct
4 Correct 88 ms 117676 KB Output is correct
5 Correct 92 ms 117724 KB Output is correct
6 Correct 92 ms 117724 KB Output is correct
7 Correct 93 ms 117724 KB Output is correct
8 Correct 94 ms 117724 KB Output is correct
9 Correct 94 ms 117724 KB Output is correct
10 Correct 95 ms 117724 KB Output is correct
11 Correct 89 ms 117724 KB Output is correct
12 Correct 89 ms 117724 KB Output is correct

Subtask #3
0 / 60.0

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