제출 #1298103

#제출 시각아이디문제언어결과실행 시간메모리
1298103rana_azkaBouquet (EGOI24_bouquet)C++20
24 / 100
67 ms17332 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int INF = 1e18;
const int MOD = 1e9+7;
const int MAXN = 2e5;

int n, m;
int arr[MAXN+5][5];
int dp[MAXN+5];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

void mulaidarinol(){}

void solve(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> arr[i][0] >> arr[i][1];

    vector<pair<int, int>> v;
    for(int i = 1; i <= n; i++) v.push_back({i - arr[i][0], i});
    sort(v.begin(), v.end());

    int mx = 0;
    for(auto [kiri, idx] : v){
        while(!pq.empty() && pq.top().first < idx && pq.top().second < kiri){
            mx = max(dp[pq.top().second], mx);
            pq.pop();
        }

        dp[idx] = mx + 1;

        pq.push({idx + arr[idx][1], idx});
    }

    int ans = 0;
    for(int i = 1; i <= n; i++){
        ans = max(dp[i], ans);
        // cerr << "\n" << i << " : " << dp[i] << endl;
    }

    cout << ans << endl;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int tc = 1;
    // cin >> tc;
    while(tc--){
        // mulaidarinol();
        solve();
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...