Submission #462608

#	Time	Username	Problem	Language	Result	Execution time	Memory
462608		JovanB	Jump (BOI06_jump)	C++17	100 / 100	12 ms	3148 KiB

jump

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
int mat[205][205];
 
struct bigint{
    vector <int> broj;
    void output(){
        int n = broj.size();
        for(int i=n-1; i>=0; i--) cout << broj[i];
        return;
    }
    bigint operator + (const bigint &a){
        int n = broj.size();
        int m = a.broj.size();
        bigint res;
        for(int i=0; i<max(n, m)+5; i++) res.broj.push_back(0);
        for(int i=0; i<max(n, m)+1; i++){
            if(i < n) res.broj[i] += broj[i];
            if(i < m) res.broj[i] += a.broj[i];
            res.broj[i+1] += res.broj[i]/10;
            res.broj[i] %= 10;
        }
        while(res.broj[res.broj.size()-1] == 0 && res.broj.size() > 1) res.broj.pop_back();
        return res;
    }
 
} dp[205][205];
 
void output(bigint x){
    int n = x.broj.size();
    for(int i=n-1; i>=0; i--) cout << x.broj[i];
    return;
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cout.precision(10);
    cout<<fixed;
 
    int n;
    cin >> n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> mat[i][j];
        }
    }
    dp[n][n].broj = {1};
    for(int i=n; i>=1; i--){
        for(int j=n; j>=1; j--){
            if(i == n && j == n) continue;
            dp[i][j] = dp[i][j] + dp[i+mat[i][j]][j];
            dp[i][j] = dp[i][j] + dp[i][j+mat[i][j]];
        }
    }
    output(dp[1][1]);
    return 0;
}

• Subtask 1: 100 / 100