oj.uz

Submission #362243

# Submission time Handle Problem Language Result Execution time Memory
362243 2021-02-02T10:38:09 Z Yeboi Tents (JOI18_tents) C++14
100 / 100
 263 ms 70764 KB 
#include <bits/stdc++.h>
#define ll long long
#define mod 998244353
#define rep(i,s) for(ll i=0; i<s ; i++)
#define f(i,a,b) for(long long i(a); i<b ; i++)
#define inf -pow(10,9)
#define MAXN 100000 
const ll INF = 1000000000;
const ll N = 50005;
const ll modi = 1000000007;
const ll modi2= 1000000006;
using namespace std;

int main(){
    ll h,w;
    cin >> h >> w;
    ll dp[h+1][w+1];
    rep(i,h+1){
        rep(j,w+1){
            dp[i][j]=0;
        }
    }
    rep(i,h+1){
        dp[i][0]=1;
    }
    rep(i,w+1){
        dp[0][i]=1;
    }
    f(i,1,h+1){
        f(j,1,w+1){
            dp[i][j]=(dp[i][j]+dp[i][j-1]+modi)%modi;
            dp[i][j]=(dp[i][j]+4*i*dp[i-1][j-1] + modi)%modi;
            ll val1=(i*(i-1))/2;
            ll val2=(i*(j-1));
            if(i>1){
                ll x1=(val1*dp[i-2][j-1]+modi)%modi;
                dp[i][j]=(dp[i][j]+x1+modi)%modi;
            }
            if(j>1){
                ll x2=(val2*dp[i-1][j-2]+modi)%modi;
                dp[i][j]=(dp[i][j]+x2+modi)%modi;
            }
            
            // cout << i << " " << j << " " << dp[i][j] << endl;
        }
    }
    cout << dp[h][w]-1 << endl;
}

Subtask #1
48.0 / 48.0

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

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 3 ms 1004 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 168 ms 44140 KB Output is correct
16 Correct 12 ms 3180 KB Output is correct
17 Correct 37 ms 10092 KB Output is correct
18 Correct 46 ms 12416 KB Output is correct
19 Correct 194 ms 51328 KB Output is correct
20 Correct 155 ms 41160 KB Output is correct
21 Correct 101 ms 27244 KB Output is correct
22 Correct 100 ms 26732 KB Output is correct
23 Correct 55 ms 14956 KB Output is correct
24 Correct 263 ms 70764 KB Output is correct
25 Correct 196 ms 52588 KB Output is correct
26 Correct 231 ms 60268 KB Output is correct
27 Correct 254 ms 68204 KB Output is correct