Submission #977955

#	Time	Username	Problem	Language	Result	Execution time	Memory
977955		kilkuwu	Stove (JOI18_stove)	C++17	100 / 100	25 ms	2468 KiB

stove

#include <bits/stdc++.h>

#define nl '\n'

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int N, K;
  std::cin >> N >> K;

  std::vector<int> T(N);
  for (int i = 0; i < N; i++) {
    std::cin >> T[i];
  }

  std::sort(T.begin(), T.end());

  // split em into K parts such that a - b + .... + b - a
  // dp[i][k] = a[i] + 1 + min(dp[j][k - 1] - a[j + 1])
  // dp[i][k] = // slope trick ? 

  // dp[i][k] = // e
  // O(k * n) is easy
  // -a[j + 1] + a[j]
  // a[1] + a[n]
  // getting the k smallest lol

  std::priority_queue<int, std::vector<int>, std::greater<int>> pq;

  for (int i = 0; i + 1 < N; i++) {
    pq.push(T[i] - T[i + 1] + 1);
  }

  // 2 - 3
  // 4 - 6
  // -1 
  // -2

  int ans = T[N - 1] + 1 - T[0];

  // minimal lol

  K--;
  while (K > 0 && pq.size() && pq.top() < 0) {
    ans += pq.top();
    pq.pop();
    K--;
  }

  std::cout << ans << nl;
}

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