답안 #47599 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
47599	2018-05-05T11:00:55 Z	qoo2p5	Asceticism (JOI18_asceticism)	C++17	49 / 100	164 ms	93488 KB

asceticism

#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 = 3003;
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] * (k + 1) % MOD);
            if (k > 0) {
                add(dp[n][k], dp[n - 1][k - 1] * (n - k) % MOD);
            }
        }
    }
    
    int n, k;
    cin >> n >> k;
    cout << dp[n][k - 1] << "\n";
}

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	88 ms	46696 KB	Output is correct
2	Correct	91 ms	46820 KB	Output is correct
3	Correct	88 ms	46820 KB	Output is correct
4	Correct	87 ms	46820 KB	Output is correct
5	Correct	87 ms	46832 KB	Output is correct
6	Correct	89 ms	47012 KB	Output is correct
7	Correct	88 ms	47012 KB	Output is correct
8	Correct	87 ms	47012 KB	Output is correct
9	Correct	88 ms	47012 KB	Output is correct
10	Correct	88 ms	47012 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	88 ms	46696 KB	Output is correct
2	Correct	91 ms	46820 KB	Output is correct
3	Correct	88 ms	46820 KB	Output is correct
4	Correct	87 ms	46820 KB	Output is correct
5	Correct	87 ms	46832 KB	Output is correct
6	Correct	89 ms	47012 KB	Output is correct
7	Correct	88 ms	47012 KB	Output is correct
8	Correct	87 ms	47012 KB	Output is correct
9	Correct	88 ms	47012 KB	Output is correct
10	Correct	88 ms	47012 KB	Output is correct
11	Correct	87 ms	47012 KB	Output is correct
12	Correct	87 ms	47040 KB	Output is correct
13	Correct	88 ms	47040 KB	Output is correct
14	Correct	92 ms	47040 KB	Output is correct
15	Correct	88 ms	47040 KB	Output is correct
16	Correct	88 ms	47040 KB	Output is correct
17	Correct	87 ms	47040 KB	Output is correct
18	Correct	88 ms	47072 KB	Output is correct
19	Correct	87 ms	47072 KB	Output is correct
20	Correct	87 ms	47072 KB	Output is correct

Subtask #3
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	88 ms	46696 KB	Output is correct
2	Correct	91 ms	46820 KB	Output is correct
3	Correct	88 ms	46820 KB	Output is correct
4	Correct	87 ms	46820 KB	Output is correct
5	Correct	87 ms	46832 KB	Output is correct
6	Correct	89 ms	47012 KB	Output is correct
7	Correct	88 ms	47012 KB	Output is correct
8	Correct	87 ms	47012 KB	Output is correct
9	Correct	88 ms	47012 KB	Output is correct
10	Correct	88 ms	47012 KB	Output is correct
11	Correct	87 ms	47012 KB	Output is correct
12	Correct	87 ms	47040 KB	Output is correct
13	Correct	88 ms	47040 KB	Output is correct
14	Correct	92 ms	47040 KB	Output is correct
15	Correct	88 ms	47040 KB	Output is correct
16	Correct	88 ms	47040 KB	Output is correct
17	Correct	87 ms	47040 KB	Output is correct
18	Correct	88 ms	47072 KB	Output is correct
19	Correct	87 ms	47072 KB	Output is correct
20	Correct	87 ms	47072 KB	Output is correct
21	Correct	87 ms	47072 KB	Output is correct
22	Correct	87 ms	47072 KB	Output is correct
23	Correct	90 ms	47072 KB	Output is correct
24	Correct	88 ms	47072 KB	Output is correct
25	Correct	93 ms	47072 KB	Output is correct
26	Correct	93 ms	47072 KB	Output is correct
27	Correct	92 ms	47072 KB	Output is correct
28	Correct	114 ms	47072 KB	Output is correct
29	Correct	92 ms	47072 KB	Output is correct
30	Correct	91 ms	47072 KB	Output is correct

Subtask #4
0 / 51.0

#	결과	실행 시간	메모리	Grader output
1	Correct	88 ms	46696 KB	Output is correct
2	Correct	91 ms	46820 KB	Output is correct
3	Correct	88 ms	46820 KB	Output is correct
4	Correct	87 ms	46820 KB	Output is correct
5	Correct	87 ms	46832 KB	Output is correct
6	Correct	89 ms	47012 KB	Output is correct
7	Correct	88 ms	47012 KB	Output is correct
8	Correct	87 ms	47012 KB	Output is correct
9	Correct	88 ms	47012 KB	Output is correct
10	Correct	88 ms	47012 KB	Output is correct
11	Correct	87 ms	47012 KB	Output is correct
12	Correct	87 ms	47040 KB	Output is correct
13	Correct	88 ms	47040 KB	Output is correct
14	Correct	92 ms	47040 KB	Output is correct
15	Correct	88 ms	47040 KB	Output is correct
16	Correct	88 ms	47040 KB	Output is correct
17	Correct	87 ms	47040 KB	Output is correct
18	Correct	88 ms	47072 KB	Output is correct
19	Correct	87 ms	47072 KB	Output is correct
20	Correct	87 ms	47072 KB	Output is correct
21	Correct	87 ms	47072 KB	Output is correct
22	Correct	87 ms	47072 KB	Output is correct
23	Correct	90 ms	47072 KB	Output is correct
24	Correct	88 ms	47072 KB	Output is correct
25	Correct	93 ms	47072 KB	Output is correct
26	Correct	93 ms	47072 KB	Output is correct
27	Correct	92 ms	47072 KB	Output is correct
28	Correct	114 ms	47072 KB	Output is correct
29	Correct	92 ms	47072 KB	Output is correct
30	Correct	91 ms	47072 KB	Output is correct
31	Runtime error	164 ms	93488 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
32	Halted	0 ms	0 KB	-

답안 #47599

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 20.0 / 20.0

Subtask #3 25.0 / 25.0

Subtask #4 0 / 51.0

Subtask #1
4.0 / 4.0

Subtask #2
20.0 / 20.0

Subtask #3
25.0 / 25.0

Subtask #4
0 / 51.0