Submission #1109791

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1109791	2024-11-07T15:25:25 Z	Kirill22	Energetic turtle (IZhO11_turtle)	C++17	40 / 100	310 ms	231536 KB

turtle

#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;
    }
    vector<vector<int>> DP(N, vector<int> (t + 1));
    DP[0][1] = 1;
    for (int i = 1; i < N; i++) {
        for (int j = 2; j <= t; j++) {
            for (int pr = 0; pr < i; pr++) {
                (DP[i][j] += DP[pr][j - 1] * 1ll * cnt[pr][i] % mod) %= mod;
            }
            for (int pr = 0; pr < i; pr++) {
                (DP[i][j] += mod - DP[pr][j] * 1ll * cnt[pr][i] % mod) %= mod;
            }
        }
    }
    int ans = 0;
    for (int i = 0; i <= min(N, t); i++) {
        (ans += DP[N - 1][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	36 ms	97924 KB	Output is correct
2	Correct	36 ms	98120 KB	Output is correct
3	Correct	37 ms	98136 KB	Output is correct
4	Correct	44 ms	99144 KB	Output is correct
5	Correct	310 ms	130900 KB	Output is correct
6	Correct	40 ms	98120 KB	Output is correct
7	Correct	56 ms	100004 KB	Output is correct
8	Correct	42 ms	98120 KB	Output is correct
9	Runtime error	171 ms	206920 KB	Execution killed with signal 11
10	Runtime error	194 ms	215364 KB	Execution killed with signal 11
11	Runtime error	168 ms	200748 KB	Execution killed with signal 11
12	Runtime error	194 ms	214364 KB	Execution killed with signal 11
13	Runtime error	175 ms	197720 KB	Execution killed with signal 11
14	Runtime error	194 ms	200792 KB	Execution killed with signal 11
15	Runtime error	224 ms	230288 KB	Execution killed with signal 11
16	Runtime error	218 ms	231536 KB	Execution killed with signal 11
17	Runtime error	197 ms	206932 KB	Execution killed with signal 11
18	Runtime error	221 ms	231252 KB	Execution killed with signal 11
19	Runtime error	234 ms	229720 KB	Execution killed with signal 11
20	Runtime error	213 ms	231264 KB	Execution killed with signal 11