Submission #1055248

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055248		vjudge1	Trains (BOI24_trains)	C++17	100 / 100	398 ms	16420 KiB

Main

// 23 - 12 - 23 

#include<bits/stdc++.h>

using namespace std;

#define read() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define day() time_t now = time(0);char* x = ctime(&now);cerr<<"Right Now Is : "<<x<<"\n"

#define int long long
#define ii pair<int,int>
#define X first
#define Y second 

const long long MAX = (int)1e5 + 5;
const long long INF = (int)1e9;
const long long MOD = (int)1e9 + 7;
const int Block = 10;

int n,d[MAX],x[MAX];
int dp[MAX],f[MAX][Block + 5];

signed main(){
	
	read();
	
	cin >> n;
	for(int i = 1;i <= n;i++)cin >> d[i] >> x[i];	
	
	for(int i = n;i >= 1;i--){
		//cout << d[i] << " " << x[i] << " " << d[i] << "\n";
		dp[i] = 0;
		
		if(d[i] == 0){
			dp[i] = 1;
		}else if(d[i] > Block){
			for(int j = i + d[i];j <= min(n,i + d[i] * x[i]);j += d[i]){
				dp[i] = (dp[i] + dp[j]) % MOD;
			}
			dp[i] = (dp[i] + 1) % MOD;
		}else{
			//cout << i << " " << d[i] << "\n";
			dp[i] = 1;
			dp[i] = (dp[i] + ((i + d[i] <= n) ? (f[i + d[i]][d[i]]) : (0))) % MOD;
			//int cost1 = ((i + d[i] <= n) ? (f[i + d[i]][d[i]]) : (0));
			dp[i] = (dp[i] - ((i + d[i] * (x[i] + 1) <= n) ? (f[(i + d[i] * (x[i] + 1))][d[i]]) : 0) + MOD * MOD) % MOD;
			//int cost2 = ((i + d[i] * (x[i] + 1) <= n) ? (f[(i + d[i] * (x[i] + 1))][d[i]]) : 0);
			//cout << i << " " << cost1 << " " << cost2 << " " << d[i] << "\n";
		}
		
		//cout << dp[i] << "\n";
		for(int j = 0;j <= Block;j++){
			f[i][j] = ((i + j <= n ? f[i + j][j] : 0) + dp[i]) % MOD;
			//cout << f[i][j] << " \n"[j == Block];
		}
	}
	
	//for(int i = 1;i <= n;i++)cout << dp[i] << " \n"[i == n];
	
	cout << dp[1];
}

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