제출 #1057171

#제출 시각아이디문제언어결과실행 시간메모리
10571710npataTrains (BOI24_trains)C++17
100 / 100
452 ms791088 KiB
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define vec vector

const int MOD = 1e9 + 7;
const int SQN = 1000;


int32_t main() {
	int N;
	cin >> N;
	vec<int> D(N), X(N);

	for(int i = 0; i<N; i++) {
		cin >> D[i];
		cin >> X[i];
	}


	vec<int> f(N, 1);
	vec<vec<int>> fsum(N, vec<int>(SQN, 1));

	for(int i = N-2; i>=0; i--) {
		if(D[i] == 0) {}
		else if(D[i] >= SQN) {
			for(int j = 1; j<=X[i] && i+(j*D[i]) < N; j++) {
				f[i] += f[i+(j*D[i])];

				f[i] %= MOD;
				assert(i+(j*D[i]) < N);
			}
		}
		else {
			f[i] += ((i+D[i]) < N ? fsum[i+D[i]][D[i]] : 0ll) + MOD - (i+(X[i]+1)*D[i] < N ? fsum[i+(X[i]+1)*D[i]][D[i]] : 0ll);
			f[i] %= MOD;
		}

		for(int j = 1; j<SQN; j++) {
			fsum[i][j] = f[i] + ((i+j) < N ? fsum[i+j][j] : 0);
		}

	}

	cout << f[0] << '\n';

}
#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...