oj.uz

Submission #1062969

# Submission time Handle Problem Language Result Execution time Memory
1062969 2024-08-17T12:45:28 Z quanmcvn Trains (BOI24_trains) C++17
0 / 100
 2000 ms 27860 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Incorrect 3 ms 5180 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Incorrect 3 ms 5180 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2077 ms 27860 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Incorrect 3 ms 5180 KB Output isn't correct
3 Halted 0 ms 0 KB -