제출 #128718

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
128718		jangwonyoung	Sparklers (JOI17_sparklers)	C++14	50 / 100	2033 ms	9848 KiB

sparklers

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
int n,k;
ll t;
ll x[100001];
bool got[100001];
struct mob{
	ll fi,se;
};
mob operator+(mob x,mob y){
	ll a=max(x.fi,x.fi-x.se+y.fi);
	ll b=x.se-x.fi+y.se-y.fi+a;
	return (mob){a,b};
}
bool operator<(mob x,mob y){
	bool sx=x.fi<x.se,sy=y.fi<y.se;
	if(sx!=sy) return sx>sy;
	if(x.fi<x.se) return x.fi<y.fi;
	return x.se>y.se;
}
set<pair<mob,int> >cave;
int cp[100001],cs[100001];
mob val[100001];
bool solve(ll s){
	ll blood=s;
	for(int i=1; i<=n ;i++) cp[i]=cs[i]=i;
	cave.clear();
	for(int i=1; i<k ;i++){
		val[i]={x[i+1]-x[i],s};
		cave.insert({val[i],i});
	}
	for(int i=n; i>k ;i--){
		val[i]={x[i]-x[i-1],s};
		cave.insert({val[i],i});
	}
	for(int i=1; i<n ;i++){
		auto cur=*cave.begin();
		cave.erase(cave.begin());
		int par=cur.se+(cur.se<k)-(cur.se>k);
		cp[cs[cur.se]]=cp[par];
		cs[cp[par]]=cs[cur.se];
		if(cp[par]==k){//execute
			blood-=cur.fi.fi;
			if(blood<0) return false;
			blood+=cur.fi.se;
		}
		else{//merge
			cave.erase(cave.find({val[cp[par]],cp[par]}));
			val[cp[par]]=val[cp[par]]+val[cur.se];
			cave.insert({val[cp[par]],cp[par]});
		}
	}	
	return true;
}
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> k >> t;
	for(int i=1; i<=n ;i++){
		cin >> x[i];
	}
	ll l=0,r=1e9/t+1;
	while(l!=r){
		ll mid=(l+r)/2;
		if(solve(mid*t*2)) r=mid;
		else l=mid+1;
	}
	cout << l << endl;
}

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