Submission #157962

#	Time	Username	Problem	Language	Result	Execution time	Memory
157962		fedoseevtimofey	Asceticism (JOI18_asceticism)	C++14	49 / 100	108 ms	56952 KiB

asceticism

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 3007;

const int md = 1e9 + 7;

void add(int &a, int b) {
    a += b;
    if (a >= md) a -= md;
}

int sub(int a, int b) {
    a -= b;
    if (a < 0) a += md;
    return a;
}

int mul(int a, int b) {
    return ((ll)a * b) % md;
}

int dp[N][N];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    int n, k;
    cin >> n >> k;
    dp[1][1] = 1;
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            add(dp[i][j], mul(dp[i - 1][j], j));
            add(dp[i][j], mul(dp[i - 1][j - 1], i - j + 1));

        }
    }
    cout << dp[n][k] << '\n';
}

• Subtask 1: 4 / 4
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 0 / 51