Submission #958703

#	Time	Username	Problem	Language	Result	Execution time	Memory
958703		adaawf	Energetic turtle (IZhO11_turtle)	C++14	40 / 100	180 ms	205180 KiB

turtle

#include <iostream>
#include <queue>
using namespace std;
long long int f[1005][1005][21], dd[1005][1005], a[1005][1005];
int main() {
    int n, m, k, t, z;
    cin >> n >> m >> k >> t >> z;
    for (int i = 1; i <= k; i++) {
        int x, y;
        cin >> x >> y;
        a[x][y] = 1;
    }
    queue<pair<int, int>> q;
    f[0][0][0] = 1;
    q.push({0, 0});
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for (int i = 0; i <= t; i++) {
            f[x + 1][y][i + a[x + 1][y]] += f[x][y][i];
            f[x + 1][y][i + a[x + 1][y]] %= z;
            f[x][y + 1][i + a[x][y + 1]] += f[x][y][i];
            f[x][y + 1][i + a[x][y + 1]] %= z;
            if (dd[x + 1][y] == 0 && x < n) {
                q.push({x + 1, y});
                dd[x + 1][y] = 1;
            }
            if (dd[x][y + 1] == 0 && y < m) {
                q.push({x, y + 1});
                dd[x][y + 1] = 1;
            }
        }
    }
    long long int res = 0;
    for (int i = 0; i <= t; i++) res = (res + f[n][m][i]) % z;
    cout << res;
}

• Subtask 1: 40 / 100