oj.uz

Submission #1073048

# Submission time Handle Problem Language Result Execution time Memory
1073048 2024-08-24T08:59:12 Z coolboy19521 Energetic turtle (IZhO11_turtle) C++17
25 / 100
 2000 ms 1624 KB 
// Thanks Benq

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

using namespace std;

const int sz = 6e5 + 2;
const int sm = 30;

vector<pair<int,int>> vp;
vector<int> ps;
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;
    if (k == 0 || n == k) return 1;
	if (k == 1 || k == n - 1) return n;
    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() {
    cin.tie(nullptr)->sync_with_stdio(false);

    ll n, m, k, t, z;
    cin >> n >> m >> k >> t >> z;
    int sd = n + m + 2;
    // int sd = sz;

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

    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 ++) {
        vector<int> an(k + 2);
        for (int j = i - 1; 0 <= j; j --) {
            wz[j][i] = an[j] = 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], an[l], z), z);
        }
    }

    dp[0][1] = 1;

    for (int i = 1; i < k; i ++)
        for (int j = 0; j < i; j ++)
            for (int l = 2; l <= t + 2; 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 + 2; i ++)
        r = ad(r, dp[k - 1][i], z);

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

Subtask #1
25.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Execution timed out 2087 ms 348 KB Time limit exceeded
3 Execution timed out 2083 ms 344 KB Time limit exceeded
4 Execution timed out 2070 ms 348 KB Time limit exceeded
5 Execution timed out 2056 ms 348 KB Time limit exceeded
6 Correct 0 ms 348 KB Output is correct
7 Execution timed out 2092 ms 460 KB Time limit exceeded
8 Execution timed out 2063 ms 348 KB Time limit exceeded
9 Execution timed out 2044 ms 348 KB Time limit exceeded
10 Execution timed out 2033 ms 600 KB Time limit exceeded
11 Execution timed out 2049 ms 856 KB Time limit exceeded
12 Execution timed out 2067 ms 1504 KB Time limit exceeded
13 Execution timed out 2066 ms 1504 KB Time limit exceeded
14 Correct 8 ms 860 KB Output is correct
15 Execution timed out 2089 ms 860 KB Time limit exceeded
16 Execution timed out 2045 ms 1500 KB Time limit exceeded
17 Execution timed out 2039 ms 1500 KB Time limit exceeded
18 Correct 20 ms 1588 KB Output is correct
19 Correct 18 ms 1624 KB Output is correct
20 Execution timed out 2012 ms 1500 KB Time limit exceeded