oj.uz

Submission #165591

# Submission time Handle Problem Language Result Execution time Memory
165591 2019-11-27T14:13:53 Z jovan_b Tents (JOI18_tents) C++17
48 / 100
 2000 ms 28040 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;
            tren = mul(tren, fact[w1]);
            tren = mul(tren, fact[h1]);
            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, inv[k]);
                t2 = mul(t2, inv[h1-k]);
                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 67 ms 28024 KB Output is correct
3 Correct 68 ms 27924 KB Output is correct
4 Correct 71 ms 28024 KB Output is correct
5 Correct 70 ms 28024 KB Output is correct
6 Correct 72 ms 28024 KB Output is correct
7 Correct 72 ms 28024 KB Output is correct
8 Correct 68 ms 28024 KB Output is correct
9 Correct 136 ms 28024 KB Output is correct
10 Correct 84 ms 28028 KB Output is correct
11 Correct 73 ms 27932 KB Output is correct
12 Correct 209 ms 28040 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 67 ms 28024 KB Output is correct
3 Correct 68 ms 27924 KB Output is correct
4 Correct 71 ms 28024 KB Output is correct
5 Correct 70 ms 28024 KB Output is correct
6 Correct 72 ms 28024 KB Output is correct
7 Correct 72 ms 28024 KB Output is correct
8 Correct 68 ms 28024 KB Output is correct
9 Correct 136 ms 28024 KB Output is correct
10 Correct 84 ms 28028 KB Output is correct
11 Correct 73 ms 27932 KB Output is correct
12 Correct 209 ms 28040 KB Output is correct
13 Correct 68 ms 28000 KB Output is correct
14 Correct 67 ms 28024 KB Output is correct
15 Execution timed out 2061 ms 28024 KB Time limit exceeded
16 Halted 0 ms 0 KB -