Submission #1033593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033593		khanhtb	Trains (BOI24_trains)	C++14	100 / 100	203 ms	257908 KiB

Main

// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC targt("arch=skylake,avx2,bmi,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define pf push_front
#define vi vector<ll>
#define vii vector<vi>
#define pll pair<ll, ll>
#define vpll vector<pll>
#define all(a) a.begin(), a.end()
#define fi first
#define se second
using namespace std;
const ll mod = 1e9+7; 
const ll inf = 2e18;
const ll blocksz = 320;
const ll N = 2e5 + 8;
ll n,d[N],x[N],dp[N],pre[N][blocksz+2];
void solve(){
    cin >> n;
	for(ll i = 1; i <= n; i++) cin >> d[i] >> x[i];
	dp[n] = 1;
	for(ll b = 1; b <= blocksz; b++) pre[n][b] = dp[n];
	for(ll i = n-1; i >= 1; i--){
		dp[i] = 1;
		if(d[i] != 0){
			if(d[i] >= blocksz){
				for(ll t = 1; t <= x[i] && i+t*d[i] <= n; t++){
					dp[i] = (dp[i]+dp[i+t*d[i]])%mod;
				}
			}
			else{
				if(i+d[i]*x[i]+d[i] <= n){
					dp[i] = (dp[i]+((pre[i+d[i]][d[i]]-pre[i+d[i]*x[i]+d[i]][d[i]])%mod+mod)%mod)%mod;
				}
				else dp[i] = (dp[i]+pre[i+d[i]][d[i]])%mod;
			}
		}	
		for(ll b = 1; b <= blocksz; b++) pre[i][b] = (dp[i]+pre[i+b][b])%mod;
	}
	cout << dp[1];
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);    
    if (fopen("test.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll T = 1;
    // cin >> T;
    for (ll i = 1; i <= T; i++){
        solve();
        cout << '\n';
    }
}

Compilation message (stderr)

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

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