Submission #1033621

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033621		ara_ara	Trains (BOI24_trains)	C++17	100 / 100	202 ms	254804 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7,maxn=1e5+1,cunt=320;
int f[maxn][cunt],d[maxn],x[maxn],dp[maxn];
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n; cin>>n;
    for(int i=1;i<=n;i++) cin>>d[i]>>x[i];
    for(int i=n;i>=1;i--){
        dp[i]=1;
        if(d[i]){
            if(d[i]>cunt) for(int j=i+d[i];j<=min(n,i+x[i]*d[i]);j+=d[i]) dp[i]=(dp[i]+dp[j])%mod;
            else if(i+d[i]<=n){
                int tmp=f[i+d[i]][d[i]];
                if(i+d[i]*(x[i]+1)<=n) tmp-=f[i+d[i]*(x[i]+1)][d[i]];
                dp[i]=((dp[i]+tmp)%mod+mod)%mod;
            }
        }
        for(int j=1;j<=cunt;j++){
            f[i][j]=dp[i];
            if(i+j<=n) f[i][j]=(f[i][j]+f[i+j][j])%mod;
        }
    }
    cout<<dp[1];
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:22:20: warning: iteration 319 invokes undefined behavior [-Waggressive-loop-optimizations]
   22 |             f[i][j]=dp[i];
      |             ~~~~~~~^~~~~~
Main.cpp:21:22: note: within this loop
   21 |         for(int j=1;j<=cunt;j++){
      |                     ~^~~~~~

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