Submission #1058279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058279		ZeroCool	Trains (BOI24_trains)	C++14	100 / 100	111 ms	239408 KiB

Main

#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];
}

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