oj.uz

Submission #1073001

# Submission time Handle Problem Language Result Execution time Memory
1073001 2024-08-24T08:21:00 Z coolboy19521 Energetic turtle (IZhO11_turtle) C++17
25 / 100
 2000 ms 2516 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;
    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() {
    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][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
25.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2512 KB Output is correct
2 Execution timed out 2016 ms 2516 KB Time limit exceeded
3 Execution timed out 2044 ms 2516 KB Time limit exceeded
4 Execution timed out 2045 ms 2512 KB Time limit exceeded
5 Execution timed out 2086 ms 2512 KB Time limit exceeded
6 Correct 4 ms 2516 KB Output is correct
7 Execution timed out 2093 ms 2516 KB Time limit exceeded
8 Execution timed out 2100 ms 2512 KB Time limit exceeded
9 Execution timed out 2053 ms 2512 KB Time limit exceeded
10 Execution timed out 2077 ms 2516 KB Time limit exceeded
11 Execution timed out 2047 ms 2512 KB Time limit exceeded
12 Execution timed out 2025 ms 2516 KB Time limit exceeded
13 Execution timed out 2049 ms 2512 KB Time limit exceeded
14 Correct 50 ms 2512 KB Output is correct
15 Execution timed out 2004 ms 2512 KB Time limit exceeded
16 Execution timed out 2041 ms 2512 KB Time limit exceeded
17 Execution timed out 2051 ms 2516 KB Time limit exceeded
18 Correct 151 ms 2512 KB Output is correct
19 Correct 140 ms 2516 KB Output is correct
20 Execution timed out 2078 ms 2512 KB Time limit exceeded