Submission #1233592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233592		dssfsuper2	Bouquet (EGOI24_bouquet)	C++20	24 / 100	23 ms	2580 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

void solve(){
    int n;cin>>n;
    //max number of disjoint intervals so greedy by end
    vector<pii> es;
    for(int i = 0;i<n;i++){
        int l,r;cin>>l>>r;
        es.push_back({i+r, i-l});
    }
    sort(es.begin(), es.end());
    int m=-1e9;
    int mi = -1e9;
    int res = 0;
    //greedy should work logically
    for(int i = 0;i<n;i++){
        if(i<=mi)continue;
        pii s = {es[i].second, es[i].first};
        if(s.first>m){
            res++;
            m=i;
            mi=s.second;
        }
    }
    cout << res << '\n';
}




int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t=1;
    while(t--)solve();
}

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