Submission #1196536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196536		amanthaband	Stove (JOI18_stove)	C++20	50 / 100	1094 ms	11760 KiB

stove

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

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

    vector<vector<int>> arr;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        arr.push_back({x, x + 1});
    }

    sort(arr.begin(), arr.end());
    vector<vector<int>> ans;
    for (int i = 0; i < n; i++) {
        if (ans.empty() || arr[i][0] > ans.back()[1]) {
            ans.push_back(arr[i]);
        } else {
            ans.back()[1] = max(ans.back()[1], arr[i][1]);
        }
    }

    while ((int)ans.size() > k) {
        int mn = INT_MAX, idx = -1;
        for (int i = 0; i < (int)ans.size() - 1; i++) {
            int gap = ans[i + 1][0] - ans[i][1];
            if (gap < mn) mn = gap, idx = i;
        }
        vector<int> merged = {min(ans[idx][0], ans[idx + 1][0]), max(ans[idx][1], ans[idx + 1][1])};
        ans.erase(ans.begin() + idx);
        ans.erase(ans.begin() + idx);
        ans.insert(ans.begin() + idx, merged);
    }

    int total = 0;
    for (auto& v : ans) total += v[1] - v[0];
    cout << total << endl;

    return 0;
}

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