oj.uz

Submission #317942

# Submission time Handle Problem Language Result Execution time Memory
317942 2020-10-31T01:00:16 Z jainbot27 Tents (JOI18_tents) C++17
100 / 100
 1780 ms 36088 KB 
#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()

#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const char nl = '\n';
const int mxN = 3e3 + 10;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;

int fact[mxN*2];
int add(int x, int y){ x += y; while(x >= MOD) x -= MOD; while(x < 0) x += MOD; return x; } void ad(int &x, int y) {x = add(x, y);}
int sub(int x, int y){ x -= y; while(x >= MOD) x -= MOD; while(x < 0) x += MOD; return x; } void sb(int &x, int y) {x = sub(x, y);}
int mul(int x, int y){ return ((int64_t)x * (int64_t)y) % MOD; } void ml(int &x, int y) {x = mul(x, y);}
int binpow(int x, int y){ int z = 1; while(y > 0) { if(y % 2 == 1) z = mul(z, x); x = mul(x, x); y /= 2; } return z; }
int inv(int x){ return binpow(x, MOD - 2); }
int divide(int x, int y){ return mul(x, inv(y)); }
void precalc(){ fact[0] = 1; for(int i = 1; i < 2*mxN; i++) fact[i] = mul(i, fact[i - 1]); }
int choose(int n, int k){ if(k > n) return 0; return divide(fact[n], mul(fact[n - k], fact[k])); }

int n, m, ans = 0, dp[mxN][mxN];

int c2(int x){
    return mul(x, mul(sub(x,1), inv(2)));
}

int d(int h, int v){
    if(dp[h][v]!=-1) return dp[h][v];
    if(h <= 0 || v <= 0) return 1;
    int res = 0;
    ad(res, d(h-1, v));
    ad(res, mul(4*v, d(h-1, v-1)));
    ad(res, mul(c2(v), d(h-1, v-2)));
    ad(res, mul(v, mul(h-1, d(h-2, v-1))));
    return dp[h][v] = res;
};
int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    memset(dp, -1, sizeof dp);
    cin >> n >> m;
    cout << sub(d(n, m), 1) << nl;
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 35840 KB Output is correct
2 Correct 20 ms 35840 KB Output is correct
3 Correct 21 ms 35832 KB Output is correct
4 Correct 20 ms 35840 KB Output is correct
5 Correct 22 ms 35840 KB Output is correct
6 Correct 25 ms 35840 KB Output is correct
7 Correct 22 ms 35840 KB Output is correct
8 Correct 24 ms 35840 KB Output is correct
9 Correct 21 ms 35840 KB Output is correct
10 Correct 30 ms 35840 KB Output is correct
11 Correct 20 ms 35840 KB Output is correct
12 Correct 39 ms 35840 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 35840 KB Output is correct
2 Correct 20 ms 35840 KB Output is correct
3 Correct 21 ms 35832 KB Output is correct
4 Correct 20 ms 35840 KB Output is correct
5 Correct 22 ms 35840 KB Output is correct
6 Correct 25 ms 35840 KB Output is correct
7 Correct 22 ms 35840 KB Output is correct
8 Correct 24 ms 35840 KB Output is correct
9 Correct 21 ms 35840 KB Output is correct
10 Correct 30 ms 35840 KB Output is correct
11 Correct 20 ms 35840 KB Output is correct
12 Correct 39 ms 35840 KB Output is correct
13 Correct 21 ms 35840 KB Output is correct
14 Correct 21 ms 35968 KB Output is correct
15 Correct 1160 ms 36068 KB Output is correct
16 Correct 34 ms 35840 KB Output is correct
17 Correct 137 ms 35832 KB Output is correct
18 Correct 292 ms 35832 KB Output is correct
19 Correct 1331 ms 36088 KB Output is correct
20 Correct 1033 ms 36048 KB Output is correct
21 Correct 609 ms 36088 KB Output is correct
22 Correct 700 ms 35960 KB Output is correct
23 Correct 464 ms 36088 KB Output is correct
24 Correct 1780 ms 36080 KB Output is correct
25 Correct 1292 ms 36056 KB Output is correct
26 Correct 1499 ms 36072 KB Output is correct
27 Correct 1674 ms 36088 KB Output is correct