Submission #730096

#	Time	Username	Problem	Language	Result	Execution time	Memory
730096		thimote75	Jump (BOI06_jump)	C++14	85 / 100	2 ms	468 KiB

jump

#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 / 100