제출 #1049411

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1049411		YassirSalama	Trains (BOI24_trains)	C++17	100 / 100	186 ms	256848 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#ifdef IOI
template<typename T>
void dbg(const T&t){
    cout<<t<<endl;
}
template<typename T,typename... Args>
void dbg(const T& t,const Args&... args){
    cout<<t<<" , ";
    dbg(args...);
}
#define dbg(...) cout<<"("<<#__VA_ARGS__<<"): ";dbg(__VA_ARGS__);
#else
#define dbg(...) 1337;
#endif
#define F first
#define S second
const int maxn=1e5+100;
const int mod=1e9+7;
signed main(){
    int n;
    cin>>n;
    vector<pair<int,int>> v(n);
    for(int i=0;i<n;i++){
        cin>>v[i].F>>v[i].S;
    }
    int dp[n];
    int t=sqrt(n)+1;
    vector<vector<int>> cnt(n,vector<int>(t+2,0));
    memset(dp,0,sizeof(dp));
    for(int i=n-1;i>=0;i--){
        dp[i]=1;
        int a=v[i].F;
        int b=v[i].S;
        if(a==0||b==0) {
            for(int j=1;j<=t;j++) {
                cnt[i][j]=dp[i];
                if(i+j<n) cnt[i][j]+=cnt[i+j][j];
                cnt[i][j]%=mod;     
            }
            continue;
        }
        if(a<=t){
            if(i+a<n)
                dp[i]+=cnt[i+a][a]%mod;
            dp[i]%=mod;
            if(i+b*a+a<n) dp[i]-=cnt[i+b*a+a][a];
            dp[i]%=mod;
            if(dp[i]<0) dp[i]+=mod;
        }else{
            int j=i;
            while(b){
                b--;
                j+=a;
                if(j>=n) break;
                dp[i]+=dp[j];
                dp[i]%=mod;
            }
        }
        for(int j=1;j<=t;j++) {
            cnt[i][j]=dp[i];
            if(i+j<n) cnt[i][j]+=cnt[i+j][j];         
            cnt[i][j]%=mod;
        }
    }
    dp[0]%=mod;
    if(dp[0]<0) dp[0]+=mod;
    cout<<dp[0]<<endl;
}

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