제출 #1311003

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311003		discontinuous	Stove (JOI18_stove)	C++20	100 / 100	21 ms	9416 KiB

stove

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define int long long

const int MOD = 1e9 + 7;
const int INF = 1e15;
const int N = 1e6;

int n, m, k, a, b, c, d, h, l, r, q, u, v, x, y;
vector<int> arr(N);

void solve() {
	cin >> n >> k;

	vector<int> gaps;

	h = 0;
	m = 1;
	c = 0;
	cin >> arr[1];

	for(int i = 2; i<=n; i++) {
		cin >> arr[i];
		if(arr[i] > arr[i-1] + 1) {
			gaps.pb(arr[i]-arr[i-1]-1);
			c += m;
			m = 1;
			h++;
		}
		else {
			m++;
		}
	}

	c += m;
	h++;

	if(k>=h) {
		cout << c; return;
	}
	
	sort(gaps.begin(), gaps.end());
	// cout << c << " ";
	for(int i = 0; i<h-k; i++) {
		c += gaps[i];
		// cout << gaps[i] << " ";
	}
	cout << c;
}

int32_t main() {
    ios::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

	int tc = 1;
	// cin >> tc;

	while(tc--) {
		solve();
		cout << "\n";
	}

	return 0;
}

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