Submission #1110871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110871		Marco_Escandon	Trains (BOI24_trains)	C++11	100 / 100	330 ms	257352 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const string ny[2] = {"No", "Yes"};
#define x first
#define y second
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    ll n;
    cin>>n;
    vector<pair<ll,ll>> cad(n);
    for(int i=0; i<n; i++)
    {
        cin>>cad[i].x>>cad[i].y;
        cad[i].x=min(n+5,cad[i].x);
        cad[i].y=min(n+5,cad[i].y);
    }
    vector<ll> dp(n+3,1);
    vector<vector<ll>> dp2(n+3,vector<ll>(sqrt(n)+3,0));
    for(int i=n-1; i>-1; i--)
    {
        if(cad[i].x==0||cad[i].y==0){
            for(int j=1; j<=sqrt(n); j++)
            {
                if(i+j<n)
                dp2[i][j]=dp2[i+j][j];
                dp2[i][j]+=dp[i];
                dp2[i][j]%=MOD;
            }continue;
 
        } 
        if(cad[i].x>=sqrt(n))
        {
            for(int j=1; j<=cad[i].y&&cad[i].x*j+i<n; j++)
            {
                dp[i]+=dp[j*cad[i].x+i];
                dp[i]%=MOD;
            }
        }
        else
        {
            if(i+cad[i].x<n)
            dp[i]+=dp2[i+cad[i].x][cad[i].x];
            if(i+cad[i].x*(cad[i].y+1)<n)dp[i]-=dp2[i+cad[i].x*(cad[i].y+1)][cad[i].x];
            dp[i]%=MOD;dp[i]+=MOD;dp[i]%=MOD;
        }
        for(int j=1; j<=sqrt(n); j++)
        {
            if(i+j<n)
            dp2[i][j]=dp2[i+j][j];
            dp2[i][j]+=dp[i];
            dp2[i][j]%=MOD;
        }
        //cout<<dp[i]<<" ";
    }
    cout<<dp[0];
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 34 / 34
• Subtask 5: 29 / 29