Submission #1037269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037269		Ludissey	Trains (BOI24_trains)	C++17	100 / 100	199 ms	256012 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
using namespace std;
const int MOD=1e9+7;
vector<vector<int>> reps;
vector<int> d,x,dp;
int sq,n;

int mod(int v){
    return (v+MOD)%MOD;
}

int calc(int i, int _d){
    int ret=0;
    if(_d<sq){
        if(i+_d<n){
            if(_d>0) ret=mod(reps[i+_d][_d]);
        }
    } else{
        if(_d>0) for (int j = i+_d; j < n; j+=_d) ret=mod(ret+dp[j]);
    }
    return ret;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    d.resize(n); x.resize(n);
    for (int i = 0; i < n; i++) cin >> d[i] >> x[i];
    sq=sqrt(n);
    reps.resize(n,vector<int>(sq+1,0));
    dp.resize(n,1);
    for (int i = n-1; i >= 0; i--) {
        dp[i]+=calc(i, d[i]);
        if((d[i]*(x[i]))+i<n&&d[i]>0){
            dp[i]=mod(dp[i]-calc((d[i]*(x[i]))+i, d[i]));
        }
        for (int j = 1; j <= sq; j++)
        {
            reps[i][j]=dp[i];
            if(i+j<n) reps[i][j]=mod(reps[i][j]+reps[i+j][j]);
        }
    }
    cout << mod(dp[0]) << "\n";
    return 0;
}

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