oj.uz

Submission #1109787

# Submission time Handle Problem Language Result Execution time Memory
1109787 2024-11-07T15:21:49 Z Kirill22 Energetic turtle (IZhO11_turtle) C++17
40 / 100
 351 ms 232016 KB 
#include "bits/stdc++.h"

using namespace std;

int mod;
int C[5000][5000];

int choose(int n, int k) {
    if (k > n || k < 0) {
        return 0;
    }
    return C[n][k];
}

void solve() {
    int n, m, k, t;
    cin >> n >> m >> k >> t >> mod;
    for (int i = 0; i < 5000; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0 || j == i) {
                C[i][j] = 1 % mod;
            } else {
                C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
            }
        }
    }
    t += 2;
    vector<pair<int, int>> a = {{0, 0}, {n, m}};
    for (int i = 0; i < k; i++) {
        int x, y;
        cin >> x >> y;
        a.push_back({x, y});
    }
    std::sort(a.begin(), a.end());
    const int N = (int) a.size();
    vector<int> dp(1 << N);
    vector<vector<int>> cnt(N, vector<int> (N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (a[i].first <= a[j].first && a[i].second <= a[j].second) {
                cnt[i][j] = choose(a[j].first + a[j].second - a[i].first - a[i].second, a[j].first - a[i].first);
            }
        }
    }
    vector<int> calc(1 << N);
    for (int msk = 0; msk < (1 << N); msk++) {
        int c = 1 % mod, prev = -1;
        for (int i = 0; i < N; i++) {
            if (msk >> i & 1) {
                if (prev != -1) {
                    c = c * 1ll * cnt[prev][i] % mod;
                }
                prev = i;
            }
        }
        calc[msk] = c;
    }
    vector<int> path(N + 1);
    vector<vector<int>> mem(N + 1);
    for (int msk = 0; msk < (1 << N); msk++) {
        if (msk >> (N - 1) & 1) {
            if (msk & 1) {
                if (calc[msk]) {
                    mem[__builtin_popcount(msk)].push_back(msk);
                }
            }
        }
    }
    for (int i = N; i >= 2; i--) {
        for (auto msk : mem[i]) {
            (path[i] += calc[msk]) %= mod;
        }
        for (int j = i + 1; j <= N; j++) {
            int val = choose(j - 2, i - 2) * 1ll * path[j] % mod;
            if (j % 2 != i % 2 || 1) {
                (path[i] += mod - val) %= mod;
            } else {
                (path[i] += val) %= mod;
            }
        }
//        cout << path[i] << endl;
    }
    int ans = 0;
    for (int i = 0; i <= min(N, t); i++) {
        (ans += path[i]) %= mod;
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 98120 KB Output is correct
2 Correct 38 ms 98120 KB Output is correct
3 Correct 38 ms 98128 KB Output is correct
4 Correct 46 ms 98944 KB Output is correct
5 Correct 351 ms 130888 KB Output is correct
6 Correct 47 ms 98164 KB Output is correct
7 Correct 65 ms 99912 KB Output is correct
8 Correct 48 ms 97616 KB Output is correct
9 Runtime error 194 ms 206908 KB Execution killed with signal 11
10 Runtime error 191 ms 215308 KB Execution killed with signal 11
11 Runtime error 194 ms 198540 KB Execution killed with signal 11
12 Runtime error 214 ms 213080 KB Execution killed with signal 11
13 Runtime error 173 ms 198740 KB Execution killed with signal 11
14 Runtime error 176 ms 202876 KB Execution killed with signal 11
15 Runtime error 233 ms 232016 KB Execution killed with signal 11
16 Runtime error 223 ms 231804 KB Execution killed with signal 11
17 Runtime error 218 ms 204884 KB Execution killed with signal 11
18 Runtime error 226 ms 232000 KB Execution killed with signal 11
19 Runtime error 235 ms 228436 KB Execution killed with signal 11
20 Runtime error 231 ms 228496 KB Execution killed with signal 11