Submission #1050916

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050916		GusterGoose27	Trains (BOI24_trains)	C++17	100 / 100	122 ms	120884 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5+5;
const int MOD = 1e9+7;
const int BLOCK = 300;
typedef long long ll;
int n;

struct mint {
	int v;
	mint(int v) : v(v) {}
	mint() {v=0;}
};

mint operator+(mint a, mint b) {
	return a.v + b.v >= MOD ? mint(a.v+b.v-MOD) : mint(a.v+b.v);
}

void operator+=(mint &a, mint b) {
	a.v += b.v;
	if (a.v >= MOD) a.v -= MOD;
}

void operator-=(mint &a, mint b) {
	a.v -= b.v;
	if (a.v < 0) a.v += MOD;
}

mint pre[MAXN][BLOCK]; // i, i+j, i+2j, ...
mint dp[MAXN];
int d[MAXN], x[MAXN];

mint sum(int l, ll r, int dist) {
	mint ans;
	if (l < n) ans += pre[l][dist];
	if (r < n) ans -= pre[r][dist];
	return ans;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> d[i] >> x[i];
		if (d[i] > n) d[i] = n;
		if (x[i] > n) x[i] = n;
	}
	for (int i = n-1; i >= 0; i--) {
		dp[i].v = 1;
		ll e = (ll)d[i]*(x[i]+1) + i;
		// if (e > n) e -= d[i]*((e-n)/d[i]);
		if (d[i] < BLOCK) {
			dp[i] += sum(i+d[i], e, d[i]);
		}
		else {
			for (int j = i+d[i]; j < e && j < n; j += d[i]) dp[i] += dp[j];
		}
		for (int j = 1; j < min(BLOCK, n); j++) pre[i][j] = dp[i] + (i+j >= n ? 0 : pre[i+j][j]);
	}
	cout << dp[0].v << '\n';
}

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