oj.uz

Submission #730096

# Submission time Handle Problem Language Result Execution time Memory
730096 2023-04-25T09:00:09 Z thimote75 Jump (BOI06_jump) C++14
85 / 100
 2 ms 468 KB 
#include <bits/stdc++.h>

using namespace std;

__int128 dp[101][101];
int jump[101][101];

int n;

void update (int i, int j) {
    if (i + 1 == n && j + 1 == n) return ;
    /*cout << (long long)(dp[i][j]) << " ";
    if(j + 1 == n) cout << endl;*/

    if (i + jump[i][j] < n) dp[i + jump[i][j]][j] += dp[i][j];
    if (j + jump[i][j] < n) dp[i][j + jump[i][j]] += dp[i][j];
}
string to_string (__int128 val) {
    string S = "";
    if (val == 0) return "0";

    while (val != 0) {
        S += (char) (48 + (val % 10));
        val /= 10;
    }

    reverse(S.begin(), S.end());
    return S;
}

int main () {
    dp[0][0] = 1;

    cin >> n;

    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++)
            cin >> jump[i][j];
    
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++)
            update(i, j);
    
    cout << to_string(dp[n - 1][n - 1]) << endl;
}

Subtask #1
85.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 408 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 316 KB Output is correct
16 Incorrect 1 ms 468 KB Output isn't correct
17 Correct 1 ms 468 KB Output is correct
18 Incorrect 2 ms 468 KB Output isn't correct
19 Correct 2 ms 468 KB Output is correct
20 Incorrect 2 ms 468 KB Output isn't correct