Submission #206747

#	Time	Username	Problem	Language	Result	Execution time	Memory
206747		pavement	Stove (JOI18_stove)	C++17	100 / 100	32 ms	5500 KiB

stove

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

int N, K, C, T[100005];
vector<pair<int, int> > V;
vector<int> Y;

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		cin >> T[i];
		if (i != 1 && T[i - 1] + 1 == T[i]) {
			auto ii = V.back();
			V.pop_back();
			V.emplace_back(ii.first, T[i] + 1);
		} else V.emplace_back(T[i], T[i] + 1);
	}
	for (auto i : V)
		C += i.second - i.first;
	for (int i = 0; i < V.size() - 1; i++)
		Y.push_back(V[i + 1].first - V[i].second);
	sort(Y.begin(), Y.end());
	for (int i = 1; i <= max((int)V.size() - K, 0ll); i++) C += Y[i - 1];
	cout << C << '\n';
}

Compilation message (stderr)

stove.cpp:9:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
stove.cpp: In function 'int main()':
stove.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < V.size() - 1; i++)
                  ~~^~~~~~~~~~~~~~

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