oj.uz

Submission #1072953

# Submission time Handle Problem Language Result Execution time Memory
1072953 2024-08-24T07:47:54 Z coolboy19521 Energetic turtle (IZhO11_turtle) C++17
5 / 100
 2000 ms 2768 KB 
// Thanks Benq

#include "bits/stdc++.h"
#define ll long long
#define int ll

using namespace std;

const int sz = 1e6 + 6;
const int sm = 22;

vector<pair<int,int>> vp;
vector<int> ps;
int x[sz], y[sz];
ll wz[sm][sm];
ll dp[sm][sm];
bool sv[sz];

ll bpw(ll x, ll b, ll z) {
    ll r = 1;
    while (b) {
        if (b & 1)
            (r *= x) %= z;
        (x *= x) %= z;
        b >>= 1;
    }
    return r;
}

ll nck(ll n, ll k, ll z) {
    if (n < k || n < 0) return 0;
    ll r = 1;
    for (ll i = 0; i < (ll) ps.size(); i ++) {
        ll p = ps[i], e = 0;
        if (p > n) break;
        for (ll c = p; c <= n; c *= p)
            e += n / c;
        for (ll c = p; c <= k; c *= p)
            e -= k / c;
        for (ll c = p; c <= (n - k); c *= p)
            e -= (n - k) / c;
        (r *= bpw(p, e, z)) %= z;
    }
    return r;
}

ll gt(pair<int,int> f, pair<int,int> s, int z) {
    int xds = s.first - f.first;
    int yds = s.second - f.second;
    return nck(xds + yds, yds, z);
}

ll sb(ll a, ll b, ll z) {
    return (a + z - b) % z;
}

ll ml(ll a, ll b, ll z) {
    return a * b % z;
}

ll ad(ll a, ll b, ll z) {
    return (a + b) % z;
}

signed main() {
    for (ll i = 2; i < sz; i ++) {
        if (sv[i]) continue;
        ps.push_back(i);
        sv[i] = true;
        for (ll j = i * i; j < sz; j += i)
            sv[j] = true;
    }

    ll n, m, k, t, z;
    cin >> n >> m >> k >> t >> z;

    for (int i = 0; i < k; i ++) {
        int x, y;
        cin >> x >> y;
        vp.push_back(make_pair(x, y));
    }

    vp.push_back(make_pair(0, 0));
    vp.push_back(make_pair(n, m));

    sort(begin(vp), end(vp));
    k = vp.size();

    for (int i = 1; i < k; i ++)
        for (int j = i - 1; 0 <= j; j --) {
            wz[j][i] = gt(vp[j], vp[i], z);
            for (int l = j + 1; l < i; l ++)
                wz[j][i] = sb(wz[j][i], ml(wz[j][l], gt(vp[k], vp[i], z), z), z);
        }

    dp[0][0] = 1;

    for (int i = 1; i < k; i ++)
        for (int j = 0; j < i; j ++)
            for (int l = 1; l <= t + 1; l ++)
                dp[i][l] = ad(dp[i][l], ml(dp[j][l - 1], wz[j][i], z), z);

    ll r = 0;

    for (int i = 1; i <= t + 1; i ++)
        r = ad(r, dp[k - 1][i], z);

    cout << r << '\n';
}

Subtask #1
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2512 KB Output is correct
2 Execution timed out 2090 ms 2516 KB Time limit exceeded
3 Execution timed out 2064 ms 2516 KB Time limit exceeded
4 Execution timed out 2048 ms 2512 KB Time limit exceeded
5 Execution timed out 2053 ms 2516 KB Time limit exceeded
6 Incorrect 5 ms 2516 KB Output isn't correct
7 Execution timed out 2088 ms 2516 KB Time limit exceeded
8 Execution timed out 2032 ms 2768 KB Time limit exceeded
9 Execution timed out 2073 ms 2516 KB Time limit exceeded
10 Execution timed out 2075 ms 2516 KB Time limit exceeded
11 Execution timed out 2031 ms 2512 KB Time limit exceeded
12 Execution timed out 2020 ms 2512 KB Time limit exceeded
13 Execution timed out 2041 ms 2512 KB Time limit exceeded
14 Incorrect 78 ms 2516 KB Output isn't correct
15 Execution timed out 2093 ms 2564 KB Time limit exceeded
16 Execution timed out 2032 ms 2512 KB Time limit exceeded
17 Execution timed out 2041 ms 2512 KB Time limit exceeded
18 Incorrect 194 ms 2516 KB Output isn't correct
19 Incorrect 188 ms 2512 KB Output isn't correct
20 Execution timed out 2055 ms 2516 KB Time limit exceeded