oj.uz

Submission #922692

# Submission time Handle Problem Language Result Execution time Memory
922692 2024-02-06T02:45:28 Z Alihan_8 Tents (JOI18_tents) C++17
100 / 100
 95 ms 71004 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

const int Mod = 1e9 + 7;

template <typename _F, typename _S>
auto add(_F &x, const _S &y) -> void{
    x = (x + y) % Mod;
    if ( x < 0 ){
        x += Mod;
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int h, w; cin >> h >> w;
    vector <vector<int>> dp(h + 1, vector <int> (w + 1));
    for ( int i = 0; i <= h; i++ ){
        for ( int j = 0; j <= w; j++ ){
            if ( !i || !j ){
                dp[i][j] = 1;
                continue;
            }
            add(dp[i][j], dp[i - 1][j - 1] * 4 * j + dp[i - 1][j]);
            if ( i >= 2 ){
                add(dp[i][j], dp[i - 2][j - 1] * (i - 1) * j);
            }
            if ( j >= 2 ){
                add(dp[i][j], dp[i - 1][j - 2] * (j * (j - 1) / 2));
            }
        }
    }
    add(dp[h][w], -1);
    cout << dp[h][w];

    cout << '\n';
}

Subtask #1
48.0 / 48.0

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

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 504 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 2 ms 1116 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 61 ms 44124 KB Output is correct
16 Correct 4 ms 3164 KB Output is correct
17 Correct 14 ms 10264 KB Output is correct
18 Correct 17 ms 12648 KB Output is correct
19 Correct 70 ms 51548 KB Output is correct
20 Correct 56 ms 41308 KB Output is correct
21 Correct 39 ms 27224 KB Output is correct
22 Correct 37 ms 26808 KB Output is correct
23 Correct 22 ms 15196 KB Output is correct
24 Correct 95 ms 71004 KB Output is correct
25 Correct 71 ms 52796 KB Output is correct
26 Correct 85 ms 60508 KB Output is correct
27 Correct 94 ms 68296 KB Output is correct