Submission #1326874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326874		Faisal_Saqib	Jump (BOI06_jump)	C++20	85 / 100	3 ms	1132 KiB

jump

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=102;
const ll base=1e9;
struct bigint
{
    vector<ll> tp;    
    bigint(ll x)
    {
        while(x)
        {
            tp.push_back(x%base);
            x/=base;
        }
    }
    bigint()
    {
        tp.push_back(0);
    }
};
void print(bigint a)
{
    while(a.tp.size()>1 and a.tp.back()==0)a.tp.pop_back();
    int sa=a.tp.size();
    // cout<<"Hola "<<a.tp.size()<<endl;
    for(int i=sa-1;i>=0;i--)
    {
        cout<<a.tp[i];
    }
    cout<<endl;
}
bigint add(bigint a,bigint b)
{
    bigint c;
    int sa=a.tp.size();
    int sb=b.tp.size();
    c.tp.resize(max(sa,sb)+1,0);
    ll cry=0;
    for(int i=0;i<=max(sb,sa);i++)
    {
        ll cc=cry;
        if(i<sa)cc+=a.tp[i];
        if(i<sb)cc+=b.tp[i];
        c.tp[i]=cc%base;
        cry=cc/base;
    }
    while(c.tp.size()>1 and c.tp.back()==0)c.tp.pop_back();
    return c;
}

bigint dp[N][N];
int g[N][N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            // g[i][j]=1;
            cin>>g[i][j];
        }
    }
    dp[n][n]=1;
    for(int i=n;i>=1;i--)
    {
        for(int j=n;j>=1;j--)
        {
            if(g[i][j]==0)continue;
            if(j+g[i][j]<=n)
                dp[i][j]=add(dp[i][j],dp[i][j+g[i][j]]);
            if(i+g[i][j]<=n)
                dp[i][j]=add(dp[i][j],dp[i+g[i][j]][j]);
        }
    }
    print(dp[1][1]);
}

• Subtask 1: 85 / 100