Submission #1241895

#TimeUsernameProblemLanguageResultExecution timeMemory
1241895khanhttStove (JOI18_stove)C++20
100 / 100
13 ms1864 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; vector<ll> A(n); for(int i = 0; i < n; i++){ cin >> A[i]; } if(k >= n){ // You can put each element in its own segment cout << n << "\n"; return 0; } sort(A.begin(), A.end()); // Compute the n-1 gaps between consecutive points: vector<ll> gaps; gaps.reserve(n-1); for(int i = 1; i < n; i++){ gaps.push_back(A[i] - A[i-1]); } // Sort gaps descending: sort(gaps.begin(), gaps.end(), greater<ll>()); // Base cost is covering everything in one segment: ll cost = (A[n-1] - A[0] + 1); // Subtract the (k-1) largest (gap - 1) savings: for(int i = 0; i < k-1; i++){ cost -= (gaps[i] - 1); } cout << cost << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...