Submission #211581

#	Time	Username	Problem	Language	Result	Execution time	Memory
211581		TAOwoosh	Stove (JOI18_stove)	C++17	100 / 100	173 ms	10212 KiB

stove

#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2")
//#pragma GCC optimize ("trapv")
 
#include <bits/stdc++.h>
using namespace std;
 
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cin.exceptions(cin.failbit);
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
//#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (x).size()
#define what_is(x) cerr << #x << " is " << x << endl;
#define wis cout<<endl<<"I already speak english, bitch"<<endl<<endl;
 
typedef long long int lli;
typedef vector<lli> vi;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef pair<ii,lli> iii;
typedef long double C;
 
#define trace(args...) { string  _s =#args; replace(_s.begin(), _s.end(), ',',' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args);}
void err(istream_iterator<string> it){}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args){
    cout <<  *it  << " : " << a << endl;
    err(++it, args...);
}


int main(){
	fastio;

	lli n,k; cin>>n>>k;
	vi v(n),par,loc;
	k--;
	set<pair<int,int> > mark;
	rep(i,0,n){
		cin>>v[i];
	}
	//cout<<endl;
	//for(auto x : v) cout<<x<<" "; cout<<endl; 
	rep(i,0,n-1){
		par.pb(v[i+1]-(v[i]+1));
		loc.pb(v[i+1]-(v[i]+1));
	}
	//cout<<endl;
	//for(auto x : par) cout<<x<<" "; cout<<endl; 
	sort(all(loc));
	map<lli,lli> m;
	set<int> temp;

	for(int i=sz(loc)-1, cnt=0;i>=0 and cnt<k ;i--,cnt++){
		m[loc[i]]++;
		temp.insert(loc[i]);
	}

	rep(i,0,sz(par)){
		if(temp.count(par[i])){
			m[par[i]]--;
			if(m[par[i]]==0) temp.erase(par[i]);
			mark.insert({i,i+1});
	//		trace(i,i+1,par[i]);cout<<endl;
		}
	}

	lli ar=v[0],wyn=0;
	for(int i=0;i<n-1;i++){
		if(mark.count(mp(i,i+1))){
			wyn+=v[i]+1-ar;
			ar=v[i+1];
		}
	}
	wyn+=v[sz(v)-1]+1-ar;

	cout<<wyn<<endl;

	return 0;
}

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