Seletiva IOI 2015

gude.cpp

// Ivan Carvalho
// Gude - Seletiva IOI - OBI 2015
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	ll n,s,resposta=0LL;
	cin >> n >> s;
	deque<ll> guloso,saco;
	unordered_set<ll> checar;
	for(ll i=0LL;i<n;i++){
		ll davez;
		cin >> davez;
		if (!checar.count(davez)){
			checar.insert(davez);
			guloso.push_back(davez);
		}
	}
	sort(guloso.begin(),guloso.end());
	while(!guloso.empty()){
		if (saco.empty()){
			saco.push_back(guloso.front());
			guloso.pop_front();
			continue;
		}
		ll davez = guloso.front();
		guloso.pop_front();
		//cout << "Saco:";
		//for(int i=0;i<saco.size();i++) cout << " " << saco[i];
		//cout << endl;
		//cout << "Davez: " << davez;
		//if (!guloso.empty()) cout << " Proximo :" << guloso.front();
		//cout << endl;
		if (davez > s + saco.back()){
			guloso.push_front(davez);
			resposta += saco.back() - saco.front() + s;
			saco.clear();
		}
		else if (!guloso.empty() && 2LL*davez > guloso.front() + saco.back() + s){
			guloso.push_front(davez);
			resposta += saco.back() - saco.front() + s;
			saco.clear();
		}
		else saco.push_back(davez);
	}
	resposta += saco.back() - saco.front() + s;
	cout << resposta << endl;
	return 0;
}