oj.uz

Submission #1073039

# Submission time Handle Problem Language Result Execution time Memory
1073039 2024-08-24T08:52:23 Z coolboy19521 Energetic turtle (IZhO11_turtle) C++17
25 / 100
 2000 ms 1580 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);
    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[l], vp[i], z), 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 2 ms 1504 KB Output is correct
2 Execution timed out 2091 ms 1504 KB Time limit exceeded
3 Execution timed out 2028 ms 1580 KB Time limit exceeded
4 Execution timed out 2037 ms 1504 KB Time limit exceeded
5 Execution timed out 2041 ms 1500 KB Time limit exceeded
6 Correct 3 ms 1504 KB Output is correct
7 Execution timed out 2097 ms 1504 KB Time limit exceeded
8 Execution timed out 2025 ms 1500 KB Time limit exceeded
9 Execution timed out 2080 ms 1504 KB Time limit exceeded
10 Execution timed out 2088 ms 1504 KB Time limit exceeded
11 Execution timed out 2033 ms 1500 KB Time limit exceeded
12 Execution timed out 2009 ms 1500 KB Time limit exceeded
13 Execution timed out 2086 ms 1500 KB Time limit exceeded
14 Correct 48 ms 1504 KB Output is correct
15 Execution timed out 2003 ms 1576 KB Time limit exceeded
16 Execution timed out 2090 ms 1500 KB Time limit exceeded
17 Execution timed out 2013 ms 1500 KB Time limit exceeded
18 Correct 149 ms 1500 KB Output is correct
19 Correct 138 ms 1564 KB Output is correct
20 Execution timed out 2047 ms 1500 KB Time limit exceeded