Submission #1026470

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026470		mansur	Trains (BOI24_trains)	C++17	21 / 100	2100 ms	2904 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#define rall(s) s.rbegin(), s.rend()
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
#define s second 
#define f first

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int N = 1e5 + 1, mod = 1e9 + 7;
const ll inf = 1e18;

int sum(int x, int y) {
	x += y;
	if (x >= mod) x -= mod;
	if (x < 0) x += mod;
	return x;
}

int n, k = 1;
int d[N], x[N];

void gamicrab() {
	int dp[n + 1], val[k][k][350];
	memset(val, 0, sizeof(val));
	for (int i = n; i >= 1; i--) {
		dp[i] = 1;
		if (d[i]) {
			if (d[i] >= k) {
			 	for (int j = i + d[i], z = 1; j <= n && z <= x[i]; j += d[i], z++) {
			 		dp[i] = sum(dp[i], dp[j]);
			 	}
			}else {
				int p = min(349ll, (i + d[i] * 1ll * x[i]) / d[i] + 1);
				int vl = sum(val[d[i]][i % d[i]][i / d[i] + 1], -val[d[i]][i % d[i]][p]);
				dp[i] = sum(dp[i], vl);
			}
		}
		for (int j = 1; j < k; j++) {
			val[j][i % j][i / j] = sum(val[j][i % j][i / j + 1], dp[i]);
		}
	}
	cout << dp[1];
}

void solve() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> d[i] >> x[i];                                 
	gamicrab();
}                                                      

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	solve();
}

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