Submission #1247671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247671		lambd47	Trains (BOI24_trains)	C++20	100 / 100	334 ms	278328 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;
 
 
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
 
#define int long long
const int sqr=350;
const int MX=1e5+7;
const int MOD=1e9+7;
int dp[sqr][MX+2*sqr];
int id[sqr][sqr];//onde eu to na mod i resto j 
 
 
void solve() {
//    vector<vector<vector<int>>> dp(sqr+1);//dp[i][j][k] mod i resto j prefixo k estado besta j
    int n;cin>>n;
    vector<int> resp(n,0);
    vector<int> x(n);
    vector<int> d(n);
    for(int i=0;i<n;i++)cin>>d[i]>>x[i];
 
    for(int i=1;i<sqr;i++){
        for(int j=0;j<i;j++){
            id[i][j]=i+j;
        }
    }
 
    for(int i=n-1;i>=0;i--){
        if(d[i]<sqr){
            if(d[i]==0)resp[i]=1;
            else{
                resp[i]=1;
                resp[i]+=((dp[d[i]][id[d[i]][i%d[i]]]-dp[d[i]][max((int)0,id[d[i]][i%d[i]]-(x[i]*d[i]))])%MOD+MOD)%MOD;
                resp[i]%=MOD;
            }
        }
        else{
            int idat=i;
            while(idat+d[i]<n && x[i]--){
                idat+=d[i];
                resp[i]+=resp[idat];
                resp[i]%=MOD;
            }
            resp[i]++;
            resp[i]%=MOD;
        }
 
        for(int j=1;j<sqr;j++){
            id[j][i%j]+=j;
            dp[j][id[j][i%j]]=(dp[j][id[j][i%j]-j]+resp[i])%MOD;
        }
    }
    cout<<resp[0]%MOD;
    return;
 
 
 
 
}
 
int32_t main() {
    std::cin.tie(0)->sync_with_stdio(0); 
    std::cin.exceptions(std::cin.failbit);
 
    int T = 1;
//    std::cin >> T;
    while(T--) {
        solve();
    }
 
	return 0;
}
 

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