oj.uz

Submission #47597

# Submission time Handle Problem Language Result Execution time Memory
47597 2018-05-05T10:52:50 Z qoo2p5 Asceticism (JOI18_asceticism) C++17
4 / 100
 2 ms 696 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 int N = 15;
const ll MOD = (ll) 1e9 + 7;

ll fact[N], rfact[N];

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;
    }
}

ll dp[N][N];

void add(ll &x, ll y) {
    x += y;
    x %= MOD;
}

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

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(n, 1, N) {
        rep(k, 0, n) {
            add(dp[n][k], dp[n - 1][k]);
            rep(i, 1, n) {
                rep(j, 0, k) {
                    add(dp[n][k], dp[i][j] * dp[n - 1 - i][k - 1 - j] % MOD * cnk(n - 1, i) % MOD);
                }
            }
        }
    }
    
    
    int n, k;
    cin >> n >> k;
    cout << dp[n][k - 1] << "\n";
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 544 KB Output is correct
4 Correct 2 ms 544 KB Output is correct
5 Correct 2 ms 544 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 696 KB Output is correct
9 Correct 2 ms 696 KB Output is correct
10 Correct 2 ms 696 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 544 KB Output is correct
4 Correct 2 ms 544 KB Output is correct
5 Correct 2 ms 544 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 696 KB Output is correct
9 Correct 2 ms 696 KB Output is correct
10 Correct 2 ms 696 KB Output is correct
11 Incorrect 2 ms 696 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 544 KB Output is correct
4 Correct 2 ms 544 KB Output is correct
5 Correct 2 ms 544 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 696 KB Output is correct
9 Correct 2 ms 696 KB Output is correct
10 Correct 2 ms 696 KB Output is correct
11 Incorrect 2 ms 696 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 544 KB Output is correct
4 Correct 2 ms 544 KB Output is correct
5 Correct 2 ms 544 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 696 KB Output is correct
9 Correct 2 ms 696 KB Output is correct
10 Correct 2 ms 696 KB Output is correct
11 Incorrect 2 ms 696 KB Output isn't correct
12 Halted 0 ms 0 KB -