oj.uz

Submission #165761

# Submission time Handle Problem Language Result Execution time Memory
165761 2019-11-28T13:40:08 Z jovan_b Tents (JOI18_tents) C++17
100 / 100
 459 ms 32140 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 dp[3005][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 solve(int h, int w){
    if(h < 0 || w < 0) return 0;
    if(h == 0 || w == 0) return 1;
    if(dp[h][w]) return dp[h][w];
    /// hor. par
    dp[h][w] = add(dp[h][w], mul(solve(h-1, w-2), w*(w-1)/2));
    /// ver. par
    dp[h][w] = add(dp[h][w], mul(solve(h-2, w-1), mul(w, h-1)));
    /// samo jedan
    dp[h][w] = add(dp[h][w], mul(4, mul(solve(h-1, w-1), w)));
    /// nista
    dp[h][w] = add(dp[h][w], solve(h-1, w));
    return dp[h][w];
}

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);
    }
    int h, w;
    cin >> h >> w;
    cout << add(solve(h, w), MOD-1);
    return 0;
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 4 ms 1148 KB Output is correct
5 Correct 4 ms 632 KB Output is correct
6 Correct 5 ms 1400 KB Output is correct
7 Correct 4 ms 760 KB Output is correct
8 Correct 5 ms 1576 KB Output is correct
9 Correct 4 ms 888 KB Output is correct
10 Correct 6 ms 1656 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 7 ms 1912 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 4 ms 1148 KB Output is correct
5 Correct 4 ms 632 KB Output is correct
6 Correct 5 ms 1400 KB Output is correct
7 Correct 4 ms 760 KB Output is correct
8 Correct 5 ms 1576 KB Output is correct
9 Correct 4 ms 888 KB Output is correct
10 Correct 6 ms 1656 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 7 ms 1912 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 14 ms 9848 KB Output is correct
15 Correct 324 ms 29276 KB Output is correct
16 Correct 5 ms 1528 KB Output is correct
17 Correct 27 ms 4984 KB Output is correct
18 Correct 50 ms 9336 KB Output is correct
19 Correct 371 ms 31100 KB Output is correct
20 Correct 271 ms 25648 KB Output is correct
21 Correct 134 ms 16120 KB Output is correct
22 Correct 183 ms 20080 KB Output is correct
23 Correct 152 ms 19596 KB Output is correct
24 Correct 459 ms 32140 KB Output is correct
25 Correct 359 ms 27256 KB Output is correct
26 Correct 403 ms 29920 KB Output is correct
27 Correct 449 ms 31196 KB Output is correct