oj.uz

Submission #442866

# Submission time Handle Problem Language Result Execution time Memory
442866 2021-07-09T10:04:34 Z colossal_pepe Zapina (COCI20_zapina) C++17
0 / 110
 1 ms 1228 KB 
#include <iostream>
#include <cstring>
using namespace std;

#define int long long

const int MOD = 1000000007;

int n, dp[355][355];

void setup() {
    memset(dp, -1, sizeof(dp));
    for (int i = n + 1; i < 355; i++) {
        dp[i][0] = 1;
        for (int j = 1; j < 355; j++) {
            dp[i][j] = 0;
        }
    }
}

int ways(int x) {
    int ans = 1;
    for (int i = 0; i < x; i++) {
        ans *= x;
        ans %= MOD;
    }
    return ans % MOD;
}

int badWays(int p, int t) {
    if (dp[p][t] != -1) return dp[p][t] % MOD;
    dp[p][t] = 0;
    for (int i = 0; i <= t; i++) {
        if (i == p) continue;
        dp[p][t] += badWays(p + 1, t - i) % MOD;
        dp[p][t] %= MOD;
    }
    return dp[p][t] % MOD;
}

signed main() {
    cin >> n;
    setup();
    cout << ways(n) - badWays(1, n) << endl;
    return 0;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1228 KB Output isn't correct
2 Halted 0 ms 0 KB -