Submission #1268126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268126		nguyenkhangx	Trains (BOI24_trains)	C++20	100 / 100	238 ms	125284 KiB

Main

#include <bits/stdc++.h>
#define task "a"
#define ll long long
#define mems(x, y) memset(x, y, sizeof(x));
using namespace std;
const int mod = 1e9 + 7, N = 1e5 + 9;

struct pt {

};

int n, block;
int dp[N], d[N], x[N], s[329][N];

int add(int t,int x) {
    t+=x;
    if(t>=mod) t-=mod;
    if(t<0) t+=mod;
    return t;
}

void Input() {
    cin>>n;
    block=max(1,(int)sqrt(n));

    for(int i=1;i<=n;i++){
        cin>>d[i]>>x[i];
    }

    for(int i=n;i>=1;i--){
        if(d[i]==0){
            dp[i]=1;
        }

        else{
            int dd=d[i];
            int m=min(x[i],(n-i)/dd);
            ll sum=0;
            if(dd<=block) {
                int id1=i+dd;
                int id2=i+(m+1)*dd;
                if(id1<=n) {
                    sum=s[dd][id1];
                    if(id2<=n) sum=add(sum,-s[dd][id2]);
                }
            }
            else{
                for(int k=1;k<=m;k++){
                    sum=add(sum,dp[i + k * dd]);
                }
            }
            dp[i] = add(dp[i],sum+1);
        }
        for(int dd=1;dd<=block;dd++){
            int val=dp[i];
            if(i+dd<=n) {
                val=add(val,s[dd][i+dd]);
            }
            s[dd][i]=val;
        }
    }
    cout<<dp[1];
}

int main(){

    Input();
}

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