Submission #1109785

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1109785	2024-11-07T15:17:03 Z	Kirill22	Energetic turtle (IZhO11_turtle)	C++17	5 / 100	323 ms	231888 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) {
                (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

5.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	98120 KB	Output is correct
2	Incorrect	38 ms	97936 KB	Output isn't correct
3	Incorrect	36 ms	97936 KB	Output isn't correct
4	Incorrect	48 ms	98960 KB	Output isn't correct
5	Incorrect	323 ms	130888 KB	Output isn't correct
6	Incorrect	37 ms	98228 KB	Output isn't correct
7	Incorrect	53 ms	100168 KB	Output isn't correct
8	Incorrect	39 ms	98160 KB	Output isn't correct
9	Runtime error	179 ms	206796 KB	Execution killed with signal 11
10	Runtime error	173 ms	215124 KB	Execution killed with signal 11
11	Runtime error	159 ms	200588 KB	Execution killed with signal 11
12	Runtime error	167 ms	215124 KB	Execution killed with signal 11
13	Runtime error	168 ms	198740 KB	Execution killed with signal 11
14	Runtime error	169 ms	202812 KB	Execution killed with signal 11
15	Runtime error	215 ms	231888 KB	Execution killed with signal 11
16	Runtime error	223 ms	230772 KB	Execution killed with signal 11
17	Runtime error	184 ms	204896 KB	Execution killed with signal 11
18	Runtime error	220 ms	229716 KB	Execution killed with signal 11
19	Runtime error	211 ms	230488 KB	Execution killed with signal 11
20	Runtime error	228 ms	225880 KB	Execution killed with signal 11