Submission #1057171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057171		0npata	Trains (BOI24_trains)	C++17	100 / 100	452 ms	791088 KiB

Main

#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';

}

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