oj.uz

Submission #165584

# Submission time Handle Problem Language Result Execution time Memory
165584 2019-11-27T14:02:50 Z jovan_b Tents (JOI18_tents) C++17
48 / 100
 2000 ms 28152 KB 
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;

typedef long long ll;

int add(int a, int b){
    return (a+b)%MOD;
}

int mul(int a, int b){
    return ((ll)a*b)%MOD;
}

int pw(int a, int b){
    if(b == 0) return 1;
    int res = pw(a, b/2);
    res = mul(res, res);
    if(b%2) res = mul(res, a);
    return res;
}

int inv[3005];
int fact[3005];

int bin(int n, int k){
    if(n < 0 || k < 0 || n < k) return 0;
    int res = fact[n];
    res = mul(res, inv[n-k]);
    res = mul(res, inv[k]);
    return res;
}

int brackets[3005][3005];

int main(){
    ios_base::sync_with_stdio(false);

    fact[0] = inv[0] = 1;
    for(int i=1; i<=3000; i++){
        fact[i] = mul(fact[i-1], i);
        inv[i] = pw(fact[i], MOD-2);
    }
    brackets[0][0] = 1;
    for(int i=0; i<3000; i++){
        for(int j=0; j<=i; j++){
            brackets[i+1][j+1] = add(brackets[i+1][j+1], brackets[i][j]);
            if(j) brackets[i+1][j-1] = add(brackets[i+1][j-1], mul(j, brackets[i][j]));
        }
    }
    int h, w;
    cin >> h >> w;
    int res = 0;
    //cout << brackets[4][0] << "eee";
    for(int i=0; i<=h && 2*i<=w; i++){
        for(int j=0; j+2*i<=w && 2*j+i<=h; j++){
            /// i = broj hor. parova
            /// j = broj ver. parova
            int tren = 1;
            /// hor. parovi
            tren = mul(tren, bin(h, i));
            tren = mul(tren, fact[i]);
            tren = mul(tren, bin(w, 2*i));
            tren = mul(tren, brackets[2*i][0]);
            /// ver. parovi
            /// ostalo je h-i redova i w-2*i kolona
            tren = mul(tren, bin(w-2*i, j));
            tren = mul(tren, fact[j]);
            tren = mul(tren, bin(h-i, 2*j));
            tren = mul(tren, brackets[2*j][0]);
            /// sami
            /// ostalo je h-i-2*j redova i w-2*i-j kolona
            int h1 = h-i-2*j, w1 = w-2*i-j;
            int g = 0;
            for(int k=0; k<=min(h1, w1); k++){
                if(i+j+k == 0) continue;
                int t2 = 1;
                t2 = mul(t2, pw(4, k));
                t2 = mul(t2, bin(h1, k));
                t2 = mul(t2, fact[w1]);
                t2 = mul(t2, inv[w1-k]);
                g = add(g, t2);
            }
            res = add(res, mul(tren, g));
        }
    }
    cout << res;
    return 0;
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 28024 KB Output is correct
2 Correct 68 ms 28024 KB Output is correct
3 Correct 67 ms 28024 KB Output is correct
4 Correct 69 ms 28024 KB Output is correct
5 Correct 68 ms 28024 KB Output is correct
6 Correct 73 ms 28152 KB Output is correct
7 Correct 71 ms 28024 KB Output is correct
8 Correct 69 ms 28024 KB Output is correct
9 Correct 67 ms 28024 KB Output is correct
10 Correct 84 ms 28024 KB Output is correct
11 Correct 67 ms 28024 KB Output is correct
12 Correct 197 ms 28152 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 28024 KB Output is correct
2 Correct 68 ms 28024 KB Output is correct
3 Correct 67 ms 28024 KB Output is correct
4 Correct 69 ms 28024 KB Output is correct
5 Correct 68 ms 28024 KB Output is correct
6 Correct 73 ms 28152 KB Output is correct
7 Correct 71 ms 28024 KB Output is correct
8 Correct 69 ms 28024 KB Output is correct
9 Correct 67 ms 28024 KB Output is correct
10 Correct 84 ms 28024 KB Output is correct
11 Correct 67 ms 28024 KB Output is correct
12 Correct 197 ms 28152 KB Output is correct
13 Correct 67 ms 28048 KB Output is correct
14 Correct 68 ms 28024 KB Output is correct
15 Execution timed out 2074 ms 28044 KB Time limit exceeded
16 Halted 0 ms 0 KB -