Submission #1298131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298131		rana_azka	Bouquet (EGOI24_bouquet)	C++20	8 / 100	42 ms	16544 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];
        arr[i][0] = min(i - 1, arr[i][0]);
        arr[i][1] = min(n - i, 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){
        // cerr << "idx : " << idx << endl;
        while(!pq.empty() && pq.top().first < idx){
            // cerr << idx << " : " << pq.top().second << endl;
            mx = max(dp[pq.top().second], mx);
            pq.pop();
        }

        // cerr << kiri - 1 + arr[kiri-1][1] << ' ' << idx << endl;
        if(kiri - 1 + arr[kiri-1][1] < idx) mx = max(dp[kiri - 1], mx);

        dp[idx] = mx + 1;

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

    int ans = 0;
    for(int i = 1; i <= n; i++){
        ans = max(dp[i], ans);
        // cerr << "dp[" << 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: 0 / 16
• Subtask 3: 0 / 28
• Subtask 4: 0 / 18
• Subtask 5: 0 / 30