oj.uz

Submission #1072944

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

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

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) {
    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 <= n; c *= p)
            e -= k / c;
        for (ll c = p; c <= n; 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;
}

int 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.emplace_back(x, y);
    }

    vp.emplace_back(0, 0);
    vp.emplace_back(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 3 ms 2008 KB Output is correct
2 Execution timed out 2088 ms 2008 KB Time limit exceeded
3 Execution timed out 2075 ms 2008 KB Time limit exceeded
4 Execution timed out 2055 ms 2004 KB Time limit exceeded
5 Execution timed out 2076 ms 2008 KB Time limit exceeded
6 Incorrect 4 ms 2004 KB Output isn't correct
7 Execution timed out 2072 ms 2008 KB Time limit exceeded
8 Execution timed out 2029 ms 2004 KB Time limit exceeded
9 Execution timed out 2013 ms 2004 KB Time limit exceeded
10 Execution timed out 2021 ms 2004 KB Time limit exceeded
11 Execution timed out 2056 ms 2008 KB Time limit exceeded
12 Execution timed out 2027 ms 2004 KB Time limit exceeded
13 Execution timed out 2040 ms 2008 KB Time limit exceeded
14 Incorrect 94 ms 2004 KB Output isn't correct
15 Execution timed out 2037 ms 2008 KB Time limit exceeded
16 Execution timed out 2066 ms 2008 KB Time limit exceeded
17 Execution timed out 2037 ms 2004 KB Time limit exceeded
18 Incorrect 234 ms 2008 KB Output isn't correct
19 Incorrect 227 ms 2008 KB Output isn't correct
20 Execution timed out 2060 ms 2008 KB Time limit exceeded