1150번: 백업

https://www.acmicpc.net/problem/1150

#include<stdio.h>
#include<set>
using namespace std;
const int MAX_N = 100000;
int l[MAX_N + 1], r[MAX_N + 1], w[MAX_N + 1], n, k;
set<pair<int, int> > st;
int main() {
    int pre;
    scanf("%d %d %d", &n, &k, &pre);
    for (int i = 1; i < n; i++) {
        int x;
        scanf("%d", &x);
        w[i] = x - pre;
        l[i] = i - 1;
        r[i] = i + 1;
        st.insert({ w[i], i });
        pre = x;
    }
    int res = 0;
    for (int i = 0; i < k; i++) {
        pair<int, int> now = *st.begin();
        st.erase(now);
        res += now.first;
        int lp = l[now.second], rp = r[now.second];
        l[now.second] = l[lp];
        r[now.second] = r[rp];
        l[r[rp]] = lp == 0 ? 0 : now.second;
        r[l[lp]] = rp == n ? n : now.second;
        w[now.second] = w[lp] + w[rp] - now.first;
        if (lp != 0 && rp != n) st.insert({ w[now.second], now.second });
        st.erase({ w[lp], lp });
        st.erase({ w[rp], rp });
    }
    printf("%d", res);
    return 0;
}