제출 #1064507

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1064507		_rain_	Trains (BOI24_trains)	C++14	100 / 100	288 ms	253524 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define debug false
#define int long long

const int maxn = 1e5;
const int blocksize = trunc(sqrt(maxn));

const i64 MOD = 1e9 + 7;
int add(int a , int b){
	return ((i64)a + (i64)b + MOD*MOD) % MOD;
}
int n;
int d[maxn+2] , x[maxn+2];
int dp[maxn+2] , acc[blocksize+2][blocksize+2] , store[maxn+2][blocksize+2];

void add_to_add(int x , int jump , int val){
	if (x > n) return;
	store[x][jump] = add(store[x][jump] , val);
	
}

int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> d[i] >> x[i];
	dp[1] = 1;
	for (int i = 1; i <= n; ++i){
		for (int jump = 1; jump <= blocksize; jump++){
			int r = i % jump;
			acc[r][jump] = add(acc[r][jump] , store[i][jump]);
			dp[i] = add(dp[i] , acc[r][jump]);
		}
		if (d[i]==0) continue;
		if (d[i] <= blocksize){
			i64 jump = d[i];
			add_to_add(i + jump , jump , dp[i]);
			add_to_add(i + x[i] * jump + jump , jump , -dp[i]);
		}
		else {
			for (int j = 1; j <= x[i] && i + j * d[i] <= n; ++j){
				int nxt = i + j * d[i];
				dp[nxt] = add(dp[nxt] , dp[i]);
			}
		}
	}
	if (debug){
		cout << "DEBUG\n";
		for (int i = 1; i <= n; ++i) cout << dp[i] << ' ';
		cout << '\n';
	}
	int ans = 0;
	for (int i = 1; i <= n; ++i) ans = add(ans , dp[i]);
	cout << ans;
}

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