Submission #1298103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298103		rana_azka	Bouquet (EGOI24_bouquet)	C++20	24 / 100	67 ms	17332 KiB

Main

#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;
}

• Subtask 1: 8 / 8
• Subtask 2: 16 / 16
• Subtask 3: 0 / 28
• Subtask 4: 0 / 18
• Subtask 5: 0 / 30