Submission #1264817

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264817		NikoBaotic	Trains (BOI24_trains)	C++20	100 / 100	449 ms	89440 KiB

Main

#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

#define all(x) x.begin(), x.end()
#define sz(x) ((int) ((x).size()))
#define pb push_back
#define F first
#define S second
#define FIO ios_base::sync_with_stdio(false); cin.tie(0)

const int K = 100;
const int N = 1e5 + K * 2;
const int MOD = 1e9 + 7;

ll potM(ll x, ll k) { if (k == 0) return 1; ll a = potM(x, k / 2); if (k % 2 == 0) { return (a * a) % MOD; } else { return ((a * a) % MOD * x) % MOD; }}
ll addM(ll a, ll b) { return a + b >= MOD ? a + b - MOD : a + b; }
ll subM(ll a, ll b) { return addM(a, MOD-b); }
ll mulM(ll a, ll b) { return a * b % MOD; }
ll divM(ll a, ll b) { return mulM(a, potM(b, MOD - 2)); }

int n;
ll d[N];
ll x[N];
ll dp[N];
ll dp2[N / K + 2][K + 5][K + 5];

inline ll query2(ll bu, ll off, ll po) {
	if (off >= K) return 0;
	if (po >= K) return dp[bu * K + off];
	if (dp2[bu][off][po] != -1) return dp2[bu][off][po];

	ll ind = bu * K + off;

	ll ans = addM(query2(bu, off + po, po), dp[ind]);

	dp2[bu][off][po] = ans;
	return ans;
}

inline ll query(ll ind) {
	ll bu = ind / K;
	ll ci = d[ind];
	ll br = x[ind];

	if (ci == 0) return 1;

	ll ans = 1;
	ll cur = ind + ci;
	ll broj = br;

	while (cur / K == ind / K and cur < n and broj) {
		ans = addM(ans, dp[cur]);

		broj--;
		cur += ci;
	}

	ll zad = bu;
	ll end = ind + br * ci;

	for (int i = bu + 1; i <= (n - 1) / K; i++) {
		if (end < (i + 1) * K) {
			zad = i;
			break;
		}

		ll st = i * K;
		ll off = (ind + (st - ind + ci - 1) / ci * ci) - st;
		ll adding = query2(i, off, ci);

		ans = addM(ans, adding);
	}

	ll st = zad * K;
	broj = br - (st - ind + ci - 1) / ci;
	cur = (st - ind + ci - 1) / ci * ci + ind;

	while (zad != ind / K and cur < n and broj >= 0) {
		ans = addM(ans, dp[cur]);

		broj--;
		cur += ci;
	}

	return ans;
}

int main() {
	FIO;

	memset(dp2, -1, sizeof dp2);
	
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> d[i] >> x[i];
	}

	for (int i = n - 1; i >= 0; i--) {
		dp[i] = query(i);
	}

	cout << dp[0] << endl;

	return 0;
}

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