oj.uz

Submission #47520

# Submission time Handle Problem Language Result Execution time Memory
47520 2018-05-04T15:04:10 Z qoo2p5 Tents (JOI18_tents) C++17
100 / 100
 559 ms 71420 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back

bool mini(auto &x, const auto &y) {
    if (y < x) {
        x = y;
        return 1;
    }
    return 0;
}

bool maxi(auto &x, const auto &y) {
    if (y > x) {
        x = y;
        return 1;
    }
    return 0;
}

void run();

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    run();
    return 0;
}

const ll MOD = (ll) 1e9 + 7;

ll power(ll x, ll y) {
    if (y == 0) {
        return 1;
    }
    if (y % 2 == 0) {
        ll t = power(x, y / 2);
        return t * t % MOD;
    } else {
        return power(x, y - 1) * x % MOD;
    }
}

const int N = 3003;

int H, W;
ll g[N];
ll f[N][N];
ll fact[N], rfact[N];

ll cnk(int n, int k) {
    if (k > n) {
        return 0;
    }
    return fact[n] * rfact[n - k] % MOD * rfact[k] % MOD;
}

ll dp[N][N];

ll get(int w, int h) {
    if (w < 0 || h < 0) {
        return 0;
    }
    return dp[w][h];
}

void run() {
    fact[0] = 1;
    rep(i, 1, N) {
        fact[i] = fact[i - 1] * i % MOD;
    }
    rep(i, 0, N) {
        rfact[i] = power(fact[i], MOD - 2);
    }
    
    dp[0][0] = 1;
    rep(w, 1, N) {
        rep(h, 1, N) {
            ll res = get(w - 2, h - 1) * cnk(w, 2) % MOD;
            res = (res + 4 * w * get(w - 1, h - 1) % MOD) % MOD;
            res = (res + w * (h - 1) * get(w - 1, h - 2) % MOD) % MOD;
            dp[w][h] = res;
        }
    }
    
    ll ans = 0;
    cin >> H >> W;
    rep(h, 1, H + 1) {
        rep(w, 1, W + 1) {
            ans = (ans + get(w, h) * cnk(W, w) % MOD * cnk(H, h) % MOD) % MOD;
        }
    }
    
    cout << ans << "\n";
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 71160 KB Output is correct
2 Correct 235 ms 71160 KB Output is correct
3 Correct 221 ms 71160 KB Output is correct
4 Correct 218 ms 71160 KB Output is correct
5 Correct 220 ms 71160 KB Output is correct
6 Correct 219 ms 71216 KB Output is correct
7 Correct 233 ms 71372 KB Output is correct
8 Correct 220 ms 71372 KB Output is correct
9 Correct 219 ms 71372 KB Output is correct
10 Correct 221 ms 71372 KB Output is correct
11 Correct 227 ms 71372 KB Output is correct
12 Correct 234 ms 71372 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 71160 KB Output is correct
2 Correct 235 ms 71160 KB Output is correct
3 Correct 221 ms 71160 KB Output is correct
4 Correct 218 ms 71160 KB Output is correct
5 Correct 220 ms 71160 KB Output is correct
6 Correct 219 ms 71216 KB Output is correct
7 Correct 233 ms 71372 KB Output is correct
8 Correct 220 ms 71372 KB Output is correct
9 Correct 219 ms 71372 KB Output is correct
10 Correct 221 ms 71372 KB Output is correct
11 Correct 227 ms 71372 KB Output is correct
12 Correct 234 ms 71372 KB Output is correct
13 Correct 234 ms 71372 KB Output is correct
14 Correct 227 ms 71372 KB Output is correct
15 Correct 394 ms 71372 KB Output is correct
16 Correct 231 ms 71372 KB Output is correct
17 Correct 258 ms 71372 KB Output is correct
18 Correct 265 ms 71420 KB Output is correct
19 Correct 444 ms 71420 KB Output is correct
20 Correct 398 ms 71420 KB Output is correct
21 Correct 326 ms 71420 KB Output is correct
22 Correct 326 ms 71420 KB Output is correct
23 Correct 270 ms 71420 KB Output is correct
24 Correct 542 ms 71420 KB Output is correct
25 Correct 455 ms 71420 KB Output is correct
26 Correct 502 ms 71420 KB Output is correct
27 Correct 559 ms 71420 KB Output is correct