Submission #757739

#	Time	Username	Problem	Language	Result	Execution time	Memory
757739		nikoebanoidze	Stove (JOI18_stove)	C++14	100 / 100	84 ms	6812 KiB

stove

#include <bits/stdc++.h>

#define ll long long
#define pii pair<int,int>
#define pb push_back
#define fir first
#define sec second

using namespace std;

int main() {
	int n,k;
	cin>>n>>k;
	
	int t[n+1];
	for(int i=1;i<=n;i++)
		cin>>t[i];
		
	set <pii> s;
	
	int T[n+1]={};
	
	for(int i=2;i<=n;i++)
		s.insert({t[i]-t[i-1]-1,i});
	
	int cnt=0;
	
	for(auto it=s.begin();it!=s.end() and cnt<n-k;it++){
		pii cur=*it;
		cnt++;
		T[cur.sec]=1;
	}
	
	T[1]=1;
	
	for(int i=2;i<=n;i++){
		if(T[i]==1) T[i]=T[i-1]+t[i]-t[i-1];
		if(T[i]==0) T[i]=T[i-1]+1;
	}
	
	cout<<T[n];
	
    return 0;
}

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