Submission #1194322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194322		Unforgettablepl	Trains (BOI24_trains)	C++20	8 / 100	323 ms	4220 KiB

Main

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

#define int long long

const int SQRT = 0;

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];
            DP[i]+=prefix[i][j];
        }
        ans+=DP[i];
        if(d[i]<=SQRT){
            prefix[i][d[i]]+=DP[i];
            if(i+(x[i]+1ll)*d[i]<=N)prefix[i+(x[i]+1ll)*d[i]][d[i]]-=DP[i];
        } else {
            for(int j=1;j<=x[i];j++){
                if(j*d[i]+i>N)break;
                DP[j*d[i]+i]+=DP[i];
            }
        }
    }
    cout << ans << '\n';
}

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