Submission #1194323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194323		Unforgettablepl	Trains (BOI24_trains)	C++20	100 / 100	453 ms	398104 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int SQRT = 500;
const int modulo = 1e9+7;

int32_t main(int32_t argc,char* argv[]){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<int> d(N+1);
    vector<int> x(N+1);
    for(int i=1;i<=N;i++){
        cin >> d[i] >> x[i];
    }
    vector<int> DP(N+1);
    vector prefix(N+1,vector<int>(SQRT+1));
    DP[1]++;
    int ans = 0;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=SQRT;j++){
            if(i-j<0)continue;
            prefix[i][j]+=prefix[i-j][j];
            prefix[i][j]%=modulo;
            DP[i]+=prefix[i][j];
            DP[i]%=modulo;
        }
        ans+=DP[i];
        ans%=modulo;
        if(d[i]<=SQRT){
            prefix[i][d[i]]+=DP[i];
            prefix[i][d[i]]%=modulo;
            if(i+(x[i]+1ll)*d[i]<=N){
                prefix[i+(x[i]+1ll)*d[i]][d[i]]+=modulo-DP[i];
                prefix[i+(x[i]+1ll)*d[i]][d[i]]%=modulo;
            }
        } else {
            for(int j=1;j<=x[i];j++){
                if(j*d[i]+i>N)break;
                DP[j*d[i]+i]+=DP[i];
                DP[j*d[i]+i]%=modulo;
            }
        }
    }
    cout << ans << '\n';
}

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