Submission #1360029

#TimeUsernameProblemLanguageResultExecution timeMemory
1360029biserailievaBouquet (EGOI24_bouquet)C++20
24 / 100
54 ms2596 KiB
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;

    // ќе чуваме интервали (L, R)
    vector<pair<int,int>> seg;

    for(int i = 0; i < n; i++)
    {
        int l, r;
        cin >> l >> r;

        // SUBTASK: r = 0, па r го игнорираме

        // ако лево бара повеќе отколку што постои, го скратуваме
        l = min(l, i);

        // интервалот на влијание:
        int L = i - l;   // почеток на забраната
        int R = i;       // крај (самото лале)

        seg.push_back({L, R});
    }

    // сортирање по крај на интервал (R)
    // ова е клучно за greedy да биде оптимален
    sort(seg.begin(), seg.end(), [](auto a, auto b){
        return a.second < b.second;
    });

    int last = -1; // последниот избран крај
    int ans = 0;

    // greedy избор
    for(auto [L, R] : seg)
    {
        // ако овој интервал не се преклопува со претходниот
        if(L > last)
        {
            ans++;      // земаме го
            last = R;   // ажурираме крај
        }
    }

    cout << ans << "\n";
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...