Submission #1196538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196538		amanthaband	Stove (JOI18_stove)	C++20	50 / 100	1097 ms	2492 KiB

stove

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

int main() {
    int n, k, x;
    cin >> n >> k;
    vector<pair<int, int>> intervals;
    while (n--) {
        cin >> x;
        intervals.emplace_back(x, x + 1);
    }

    sort(intervals.begin(), intervals.end());
    vector<pair<int, int>> merged;
    for (auto& [l, r] : intervals) {
        if (merged.empty() || l > merged.back().second)
            merged.emplace_back(l, r);
        else
            merged.back().second = max(merged.back().second, r);
    }

    while ((int)merged.size() > k) {
        int min_gap = INT_MAX, idx = -1;
        for (int i = 0; i + 1 < merged.size(); i++) {
            int gap = merged[i + 1].first - merged[i].second;
            if (gap < min_gap) min_gap = gap, idx = i;
        }
        pair<int, int> comb = {
            min(merged[idx].first, merged[idx + 1].first),
            max(merged[idx].second, merged[idx + 1].second)
        };
        merged.erase(merged.begin() + idx, merged.begin() + idx + 2);
        merged.insert(merged.begin() + idx, comb);
    }

    int total = 0;
    for (auto& [l, r] : merged) total += r - l;
    cout << total << endl;
}

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