oj.uz

답안 #1109785

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1109785 2024-11-07T15:17:03 Z Kirill22 힘 센 거북 (IZhO11_turtle) C++17
5 / 100
 323 ms 231888 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) {
                (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

# 결과 실행 시간 메모리 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