| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1148538 | hynmj | Bouquet (EGOI24_bouquet) | C++20 | 0 ms | 0 KiB |
//~~~~~~~~~~~~~MJ®™~~~~~~~~~~~~~
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#define rep1(n) for(ll i=0; i<(ll)(n); ++i)
#define rep2(i,n) for(ll i=0; i<(ll)(n); ++i)
#define rep3(i,a,b) for(ll i=(ll)(a); i<(ll)(b); ++i)
#define rep4(i,a,b,c) for(ll i=(ll)(a); i<(ll)(b); i+=(c))
#define cut4(a,b,c,d,e,...) e
#define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define per1(n) for(ll i=((ll)n)-1; i>=0; --i)
#define per2(i,n) for(ll i=((ll)n)-1; i>=0; --i)
#define per3(i,a,b) for(ll i=((ll)a)-1; i>=(ll)(b); --i)
#define per4(i,a,b,c) for(ll i=((ll)a)-1; i>=(ll)(b); i-=(c))
#define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__)
#define ll long long
#define ln cout<<endl
#define int long long
#define Code ios_base::sync_with_stdio(0);
#define by cin.tie(NULL);
#define Hayan cout.tie(NULL);
#define append push_back
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
#define vi vector<int>
#define ret(x) {cout<<x;return;}
#define ui map<int,int>
#define pi pair<int,int>
#define ff first
#define ss second
using namespace std;
template <typename T> using v = vector<T>;
const int INF = 1e18, MOD = 1e9+7, N = 2e5+7;
int dp[N];
int d[N];
bool compare(pi a, pi b)
{
return a.second < b.second ;
}
void solve()
{
int n, k, e, m, ans = 0;
cin >> n;
// cout << n << endl;
vector<pi> a(n);
rep(n)
{
cin >> a[i].first >> a[i].second;
ok&=(i==n-1 || a[i].second<=a[i+1].second) && (i<1 || a[i].second==a[i-1].second) && ( a[i].first==a[i].second);
}
if (ok)
{
cout << (n+a[0].first)/(a[0].first+1);
return;
}
rep(n){
a[i].first = i-a[i].first;
a[i].second = i+a[i].second;
}
// sort(all(a),compare);
rep(n)
{
// cout <<i<<" "<<n<<endl;
dp[i+1]=max(dp[i+1],dp[i]);
if (a[i].first<=0)
{
dp[a[i].second]=max(1ll,dp[a[i].second]);
}
else
dp[a[i].second]=max(dp[a[i].second],dp[a[i].first-1]+1);
dp[i+1]=max(dp[i+1],dp[i]);
}
rep(N) ans=max(ans,dp[i]);
cout << ans;
// cout << a.size();
// for (auto i: a){cout << i.ff << " " << i.ss;ln;}
}
signed main(){
Code by Hayan
int ans=1;
//cout<<setprecision(1000);
// cin>>ans;
rep(ans){
// cout << "Case #" << i+1 << ": ";
solve();ln;}}