Submission #1062969

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062969		quanmcvn	Trains (BOI24_trains)	C++17	0 / 100	2077 ms	27860 KiB

Main

#include<bits/stdc++.h>
using namespace std;

using ll = int64_t;

constexpr size_t nmax = 100000 + 15;
constexpr size_t sqrt_n = 317 + 15;
constexpr ll mod = 1'000'000'000 + 7;

void add(ll& lhs, ll rhs) {
	lhs += rhs;
	lhs %= mod;
}

ll n;
bool ok[nmax][sqrt_n];
ll cd[nmax];
vector<pair<ll, ll>> bus[sqrt_n];
set<ll> ok_sll[nmax];
ll dp[nmax];

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr); std::cout.tie(nullptr);
	cin >> n;
	ll sqrt_n_real = sqrt(n);
	for (ll i = 1; i <= n; ++ i) {
		ll d, x; cin >> d >> x;
		if (x > sqrt_n_real) {
			for (ll j = 0; j < x; ++ j) {
				ll new_i = i + d * j;
				if (new_i > n) break;
				ok_sll[new_i].insert(d);
			}
			continue;
		} else {
			bus[d].emplace_back(i, x);
		}
	}
	for (ll d = 1; d <= sqrt_n_real; ++ d) {
		for (ll i = 1; i <= n; ++ i) cd[i] = 0;
		for (const auto& [i, x] : bus[d]) {
			ll l = i;
			ll r = i + d * (x - 1);
			++ cd[l];
			if (r <= n) -- cd[r];
		}
		for (ll i = d; i <= n; ++ i) {
			cd[i] += cd[i - d];
			if (cd[i] > 0) {
				ok[i][d] = true;
			}
		}
	}
	dp[1] = 1;
	for (ll i = 1; i < n; ++ i) {
		for (ll d = 1; d <= sqrt_n_real; ++ d) {
			if (ok[i][d] && i + d <= n) {
				add(dp[i + d], dp[i]);
			}
		}
		for (const auto& d : ok_sll[i]) {
			if (i + d <= n) {
				add(dp[i + d], dp[i]);
			}
		}
	}
	ll res = 0;
	for (ll i = 1; i <= n; ++ i) {
		add(res, dp[i]);
	}
	cout << res;
}

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