oj.uz

Submission #891193

# Submission time Handle Problem Language Result Execution time Memory
891193 2023-12-22T11:29:10 Z JAVA_FF Energetic turtle (IZhO11_turtle) C++14
5 / 100
 2000 ms 47248 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Execution timed out 2087 ms 348 KB Time limit exceeded
4 Execution timed out 2040 ms 344 KB Time limit exceeded
5 Execution timed out 2037 ms 344 KB Time limit exceeded
6 Execution timed out 2047 ms 348 KB Time limit exceeded
7 Execution timed out 2060 ms 348 KB Time limit exceeded
8 Execution timed out 2056 ms 348 KB Time limit exceeded
9 Execution timed out 2021 ms 1368 KB Time limit exceeded
10 Execution timed out 2055 ms 1884 KB Time limit exceeded
11 Execution timed out 2064 ms 15964 KB Time limit exceeded
12 Execution timed out 2058 ms 47208 KB Time limit exceeded
13 Execution timed out 2024 ms 39508 KB Time limit exceeded
14 Execution timed out 2063 ms 15964 KB Time limit exceeded
15 Execution timed out 2043 ms 16220 KB Time limit exceeded
16 Execution timed out 2033 ms 44632 KB Time limit exceeded
17 Execution timed out 2069 ms 43348 KB Time limit exceeded
18 Execution timed out 2060 ms 47188 KB Time limit exceeded
19 Execution timed out 2053 ms 47248 KB Time limit exceeded
20 Execution timed out 2053 ms 47196 KB Time limit exceeded