Submission #1058279

#TimeUsernameProblemLanguageResultExecution timeMemory
1058279ZeroCoolTrains (BOI24_trains)C++14
100 / 100
111 ms239408 KiB
#include <bits/stdc++.h>

using namespace std;

#define ar array
#define int long long
#define ld long double
#define crash assert(69 == 420)

const int MOD = 1e9 + 7;
const int INF = 1e9;

const int N = 1e5 + 20;
const int K = 300;
const int LOG = 20;

int n;

int dp[N];
int ans;
int sum[K][N];

void upd(int i,int x){
	for(int j = 0;j < K;j++){
		sum[j][i] = x;
		if(i + j < n)sum[j][i] += sum[j][i + j], sum[j][i] %= MOD;
	}
}


signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
	cin>>n;
	int d[n], t[n];
	for(int i = 0;i < n;i++)cin>>d[i]>>t[i];
	for(int i = n - 1;i >= 0;i--){
		dp[i] = 1;
		if(d[i] == 0){
			upd(i, dp[i]);
			continue;
		}
		if(d[i] >= K){
			for(int j = 1;j <= t[i] && i + j * d[i] < n;j++)dp[i] += dp[i + j * d[i]], dp[i] %= MOD;
		}else{
			int l = i + d[i], r = i + (t[i] + 1) * d[i];
			if(l < n)dp[i] += sum[d[i]][l];
			if(r < n)dp[i] -= sum[d[i]][r];
			dp[i] = (dp[i] % MOD + MOD) % MOD;
		}
		upd(i, dp[i]);
		
	}
//	for(int i = 0;i  <n;i++)cout<<dp[i]<<" ";
	//cout<<'\n';
	cout<<dp[0];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...