Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "bits/stdc++.h"
- #define endl "\n"
- using namespace std;
- using pii = pair<int, int>;
- void solve() {
- int n;
- cin >> n;
- vector<int> a(n);
- vector<int> b(n);
- for (int& v: a)
- cin >> v;
- for (int& v: b)
- cin >> v;
- queue<pii> q;
- q.emplace(0, 0);
- set<int> used;
- for (int i = 1; i <= n; ++i)
- used.insert(i);
- vector<int> ans(n + 1, -1);
- ans[0] = 0;
- while(q.size()) {
- auto [num, cur] = q.front();
- q.pop();
- if (cur == n) {
- break;
- }
- for (auto it = used.lower_bound(cur); it != used.end() && *it <= cur + a[n - cur - 1]; it = used.erase(it)) {
- int new_height = *it;
- if (ans[new_height - b[n - new_height - 1]] == -1) {
- ans[new_height - b[n - new_height - 1]] = num + 1;
- q.emplace(num + 1, new_height - b[n - new_height - 1]);
- }
- }
- }
- cout << ans[n] << endl;
- }
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- int tests = 1;
- //cin >> tests;
- while(tests--) {
- //auto start = chrono::high_resolution_clock::now();
- solve();
- // auto end = chrono::high_resolution_clock::now();
- // cout << endl << (chrono::duration_cast<chrono::duration<double>>(end - start)).count();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement