Submission #1288944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288944		andreim	Stove (JOI18_stove)	C++20	0 / 100	1 ms	624 KiB

stove

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

struct Inter {
    int deb, fin;
};

bool comp(const Inter& a, const Inter& b)
{
    if (a.deb == b.deb)
        return a.fin < b.fin;
    return a.deb < b.deb;
}

signed main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int nbIntervallesPre, nbAllumettes;
    cin >> nbIntervallesPre >> nbAllumettes;
    vector<Inter> intervallesPre(nbIntervallesPre);
    for (int _ = 0; _ < nbIntervallesPre; _++)
    {
        cin >> intervallesPre[_].deb;
        intervallesPre[_].fin = intervallesPre[_].deb + 1;
    }

    sort(intervallesPre.begin(), intervallesPre.end(), comp);

    vector<Inter> intervalles;
    intervalles.push_back(intervallesPre[0]);
    for (int i = 1; i < nbIntervallesPre; i++)
    {
        if (intervallesPre[i - 1].fin == intervallesPre[i].deb)
        {
            intervalles.pop_back();
            intervalles.push_back({intervallesPre[i - 1].deb, intervallesPre[i].fin});
        }
        else
            intervalles.push_back(intervallesPre[i]);
    }

    int nbIntervalles = (int)intervalles.size();
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    for (int i = 1; i < nbIntervalles; i++)
        pq.push({intervalles[i].fin - intervalles[i - 1].fin, i});

    int total = 0;
    for (int i = 0; i < nbIntervalles - nbAllumettes; i++)
    {
        total += intervalles[pq.top().second].deb - intervalles[pq.top().second - 1].fin;
        pq.pop();
    }

    for (auto inter : intervalles)
        total += (inter.fin - inter.deb);

    cout << total << "\n";

    return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 50