oj.uz

Submission #35243

# Submission time Handle Problem Language Result Execution time Memory
35243 2017-11-19T08:29:31 Z wan2000 마스코트 (JOI13_mascots) C++14
100 / 100
 266 ms 213840 KB 
#include <bits/stdc++.h>

using namespace std;

template<typename T> inline void read(T &x){
    x = 0; char ch;
    while(!isdigit(ch=getchar()));
    do{x=10*x+ch-'0';}while(isdigit(ch=getchar()));
}
template<typename T> inline void write(T x){
    if(x<=9){ putchar(x+'0'); return;}
    write(x/10); putchar(x%10+'0');
}
template<typename T> inline void writeln(T x){
    write(x); putchar('\n');
}

typedef long long ll;

const int N = 3003;
const ll MOD = 1e9+7;

int row, col, n;
ll F[N][N], Fac[N*N], BC[N][N], res;
int u = N, v = N, p = 0, q = 0;

void init(){
    Fac[0] = 1;
    for(int i = 1; i <= row*col; i++) Fac[i] = (Fac[i-1]*(ll)i)%MOD;
    for(int i = 0; i <= max(row,col); i++) BC[0][i] = 1;
    for(int i = 1; i <= max(row,col); i++){
        BC[i][i] = 1;
        for(int j = i+1; j <= max(row,col); j++){
            BC[i][j] = (BC[i-1][j-1]+BC[i][j-1])%MOD;
        }
    }
}

ll f(int x, int y, int r, int c){
    if(F[x][y]!=-1) return F[x][y];
    if(x==r&&y==c) return 1;
    ll ret = 0;
    if(x>r) ret = (ret+f(x-1,y,r,c)*Fac[y])%MOD;
    if(y>c) ret = (ret+f(x,y-1,r,c)*Fac[x])%MOD;
    return F[x][y] = ret;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    read(row); read(col);
    init();
    read(n);
    for(int i = 1; i <= n; i++){
        int x, y;
        read(x); read(y);
        u = min(u,x);
        v = min(v,y);
        p = max(p,x);
        q = max(q,y);
    }
    int x = p-u+1;
    int y = q-v+1;
    memset(F,255,sizeof(F));
    ll need = (Fac[x*y-n]*f(row,col,x,y))%MOD;
    res = (BC[u-1][row-x]*BC[v-1][col-y])%MOD;
    res = (res*need)%MOD;
    writeln(res);
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 213536 KB Output is correct
2 Correct 6 ms 213536 KB Output is correct
3 Correct 9 ms 213536 KB Output is correct
4 Correct 13 ms 213536 KB Output is correct
5 Correct 3 ms 213536 KB Output is correct
6 Correct 9 ms 213536 KB Output is correct
7 Correct 13 ms 213536 KB Output is correct
8 Correct 9 ms 213536 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 213536 KB Output is correct
2 Correct 6 ms 213536 KB Output is correct
3 Correct 6 ms 213536 KB Output is correct
4 Correct 3 ms 213536 KB Output is correct
5 Correct 0 ms 213536 KB Output is correct
6 Correct 9 ms 213536 KB Output is correct
7 Correct 3 ms 213536 KB Output is correct
8 Correct 9 ms 213536 KB Output is correct
9 Correct 3 ms 213536 KB Output is correct
10 Correct 0 ms 213536 KB Output is correct
11 Correct 6 ms 213536 KB Output is correct
12 Correct 9 ms 213536 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 213536 KB Output is correct
2 Correct 13 ms 213536 KB Output is correct
3 Correct 9 ms 213536 KB Output is correct
4 Correct 23 ms 213544 KB Output is correct
5 Correct 26 ms 213536 KB Output is correct
6 Correct 29 ms 213536 KB Output is correct
7 Correct 26 ms 213536 KB Output is correct
8 Correct 53 ms 213564 KB Output is correct
9 Correct 119 ms 213536 KB Output is correct
10 Correct 233 ms 213840 KB Output is correct
11 Correct 176 ms 213752 KB Output is correct
12 Correct 96 ms 213536 KB Output is correct
13 Correct 6 ms 213536 KB Output is correct
14 Correct 126 ms 213536 KB Output is correct
15 Correct 243 ms 213832 KB Output is correct
16 Correct 213 ms 213788 KB Output is correct
17 Correct 109 ms 213536 KB Output is correct
18 Correct 266 ms 213828 KB Output is correct