#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
int main() {
int n;
cin >> n;
vector<pair<int, int>> a(n);
for (int i = 0; i < n; i++)
{
cin >> a[i].first >> a[i].second;
}
vector<int> dp1(n), dp2(n);
dp1[0] = 1;
dp2[n-1] = 1;
for (int i = 1; i < n; i++)
{
dp1[i] = dp1[i-1];
for (int j = i-a[i].first-1; j >= 0; j--)
{
if(j+a[j].second < i) {
dp1[i] = max(dp1[i], 1+dp1[j]);
break;
}
}
dp2[n-i-1] = dp2[n-i];
for (int j = n-i+a[n-i-1].second; j < n; j++)
{
if(j-a[j].first > n-i-1) {
dp2[n-i-1] = max(dp2[n-i-1], 1+dp2[j]);
break;
}
}
}
/*for(auto i: dp1) {
cout << i << " ";
}
cout << endl;
for(auto i: dp2) {
cout << i << " ";
}
cout << endl;*/
cout << max(dp1[n-1], dp2[0]) << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |