Submission #1243988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243988		shiori_chan	Stove (JOI18_stove)	C++20	100 / 100	16 ms	972 KiB

stove

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <chrono>
#include <stack>
#include <queue>
#define all(x) x.begin(), x.end()

using namespace std;
typedef long long ll;

const int nd = 2e5 + 5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> dist(1 , (int)2e9);

stack <pair<int , int> > st;

priority_queue <int , vector <int> , greater <int> > q;

void solve(){
	int n , k; cin >> n >> k;
	int res = n;

	for(int i = 1;i <= n; ++ i){
		int v; cin >> v;
		int total_time = 1;
		while(st.size() && st.top().first + 1 == v) 
			total_time += st.top().second , st.pop();

		if(st.size()){
			q.push(v - st.top().first - 1);
			//cout << st.top().first << '\n';
			while(st.size()) st.pop();
		}
		st.push({v , total_time});
	}

	int cnt = q.size() + 1;

	while(cnt > k){
		-- cnt;
		res += q.top();
		q.pop();
	}

	cout << res;
}

signed main() {
   ios_base::sync_with_stdio(false);
   cin.tie(0);

	#define task "task" 
	if(fopen(task".inp", "r")) {
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}
	solve();

	return 0;
}

Compilation message (stderr)

stove.cpp: In function 'int main()':
stove.cpp:56:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |                 freopen(task".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
stove.cpp:57:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |                 freopen(task".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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