Submission #1033634

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033634		nathan4690	Trains (BOI24_trains)	C++14	100 / 100	174 ms	127636 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define el cout << '\n'
#define f1(i,n) for(ll i=1;i<=n;i++)
#define __file_name "B"
using namespace std;
const ll maxn = 1e5+5, inf=1e18, bsz = 320, mod=1e9+7;

ll n,d[maxn],x[maxn],dp[maxn];
int dp2[bsz][maxn];

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    if(fopen(__file_name ".inp", "r")){
        freopen(__file_name ".inp","r",stdin);
        freopen(__file_name ".out","w",stdout);
    }
    // code here
    cin >> n;
    f1(i,n) cin >> d[i] >> x[i];
    for(ll i=n;i>=1;i--){
        if(d[i] == 0 || x[i] == 0){
            dp[i] = 1;
        }else{
            if(d[i] >= bsz){
                for(ll j = 1;j<=x[i] && i + j * d[i] <= n;j++){
                    dp[i] = (dp[i] + dp[i + j * d[i]]) % mod;
                }
                dp[i] = (dp[i] + 1) % mod;
            }else{
                dp[i] = ((ll)dp2[d[i]][i + d[i]] - dp2[d[i]][min(n+1, i + d[i] * (x[i] + 1))] + 1 + mod) % mod;
            }
        }
        f1(bb, 319){
            dp2[bb][i] = (dp2[bb][min(n+1, i + bb)] + dp[i]) % mod;
        }
    }
    // f1(i,n) cout << dp[i] << ' ';el;
    cout << dp[1];
    return 0;
}

/*
Code by: Nguyen Viet Trung Nhan
Cau Giay Secondary School
*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen(__file_name ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:18:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         freopen(__file_name ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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