Submission #1370294

#TimeUsernameProblemLanguageResultExecution timeMemory
1370294itaykarnyBouquet (EGOI24_bouquet)C++20
100 / 100
24 ms6704 KiB
#include <string>
#include <algorithm>
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<math.h>

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;

pll comp(pll a, pll b) {
	if (a.first > b.first) { return a; }
	if (b.first > a.first) { return b; }
	if (a.second < b.second) { return a; }
	return b;
}

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

	ll n;
	cin >> n;
	vpll ranges(n);
	for (ll i = 0; i < n; i++) {
		ll l, r;
		cin >> l >> r;
		ranges[i] = { max(i - l, ll(0)), min(i + r, n - 1) };
	}
	vpll dp(n);
	dp[0] = { 1, ranges[0].second };
	for (ll i = 1; i < n; i++) {
		dp[i] = dp[i - 1];
		ll ind = ranges[i].first - 1;
		if (ind >= 0) {
			if (dp[ind].second < i) {
				dp[i] = comp(dp[i], pll({ dp[ind].first + 1, ranges[i].second }));
			}
		}
		dp[i] = comp(dp[i], pll({ (ind >= 0 ? dp[ind].first : 1),ranges[i].second }));
	}
	cout << dp[n - 1].first;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...