Submission #891193

#	Time	Username	Problem	Language	Result	Execution time	Memory
891193		JAVA_FF	Energetic turtle (IZhO11_turtle)	C++14	5 / 100	2087 ms	47248 KiB

turtle

#include "bits/stdc++.h"

using namespace std;


int travel(int i, int j, int N, int M, int Z,  const unordered_set<int>& trapSet) {
    if (i == N && j == M) {
        return 1; 
    }

    if (i > N || j > M || trapSet.count(i * (M + 1) + j)) {
        return 0; 
    }

    int ways = 0;

    ways = (ways + travel(i + 1, j, N, M, Z, trapSet)) % Z; 
    ways = (ways + travel(i, j + 1, N, M, Z, trapSet)) % Z; 

    return ways;
}

int countWaysToReach(int N, int M, int K, int T, int Z, const vector<pair<int, int>>& traps) {
    unordered_set<int> trapSet;

    for (const auto& trap : traps) {
        int x = trap.first;
        int y = trap.second;
        trapSet.insert(x * (M + 1) + y);
    }

    // for(auto x : trapSet){
    //     cout << x << " ";
    // }
    cout << "\n";
    return travel(0, 0, N, M, Z, trapSet);
}

int main() {
    int N, M, K, T, Z;
    cin >> N >> M >> K >> T >> Z;

    vector<pair<int, int>> traps;
    for (int i = 0; i < K; ++i) {
        int x, y;
        cin >> x >> y;
        traps.emplace_back(x, y);
    }

    int result = countWaysToReach(N, M, K, T, Z, traps);
    cout << result << endl;

    return 0;
}

• Subtask 1: 5 / 100