Submission #1244158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244158		greenbinjack	Stove (JOI18_stove)	C++20	100 / 100	16 ms	968 KiB

stove

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
 
#include <bits/stdc++.h>
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
using LL = long long;
 
#define all(V) V.begin(), V.end()
 
template <typename DT> using ordered_set = tree <DT, null_type, less <DT>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename DT> using minheap = priority_queue < DT, vector <DT>, greater <DT> >;
template <class T> bool chMax (T &x, T y) { return y > x ? x = y, 1 : 0; }
template <class T> bool chMin (T &x, T y) { return y < x ? x = y, 1 : 0; }

int main() {
  cin.tie (nullptr) -> ios_base :: sync_with_stdio (false);

  int n, k;
  cin >> n >> k;
  int last = -1;
  vector <int> diff;
  for (int i = 0, a; i < n; i++) {
    cin >> a;
    if (last == -1) last = a;
    else diff.push_back (a - last - 1), last = a;
  }
  sort (all (diff));
  LL ans = n;
  for (int i = 0; i < n - k; i++) ans += diff[i];
  cout << ans << '\n';

  return 0;   
} 

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