C++11(clang++ 3.9) 解法, 执行用时: 74ms, 内存消耗: 2020K, 提交时间: 2018-07-07 22:37:53

#include<bits/stdc++.h>
#define int64 long long
#define sqr(x) (x)*(x)
#define mk make_pair
#define pb push_back
#define fi first
#define se second
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define VI vector<int>
#define VI64 vector<int64>
#define VS vector<string>
#define PII pair<int,int>
#define PDD pair<double,double>
#define VPII vector< PII >
#define SZ(x) ((int)(x).size())
#define N 120000
using namespace std;
const double pi=acos(-1);
set<PDD > Q;
typedef set<PDD >::iterator It;
int a[N],b[N],n,K;
int64 c[N];

void reassign(It p,int flag,double val){
	PDD tmp=*p;
	if(flag==1)tmp.fi=val;
	if(flag==2)tmp.se=val;
	Q.erase(p);
	Q.insert(tmp);
}
void del(It p){
	It pre=p; pre--;
	reassign(pre,2,pre->se+p->se);
	Q.erase(p);
}
double Get_len(It p){
	It pre=p; pre--;
	return p->first-pre->first;
}
int main(){
	scanf("%d%d",&n,&K);
	rep(i,1,n)scanf("%d%d%lld",&a[i],&b[i],&c[i]),c[i]+=c[i-1];
	Q.insert(mk(-1e30,0));
	Q.insert(mk(-1e29,0));
	Q.insert(mk(c[n-1],0));
	for(int i=n;i>=1;--i){
		//delete tails
		for(;;){
			It p=Q.end(); p--;
			double len=Get_len(p);
			if(p->fi-len>=c[i-1]){
				del(p);
				continue;
			}
			if(p->first>c[i-1])
				reassign(p,1,c[i-1]);
			break;
		}
		//
		double bandwidth=b[i],vol=a[i],t0=c[i-1];
		for(;vol>0;){
			It p=Q.end(); p--;
			It q=p; q--;
			double k1=p->se,k2=p->se+q->se;
			double vol1=Get_len(p)*(K-k1),
				   vol2=vol1+Get_len(q)*(K-k2),
				   volp=Get_len(p)*(k1-k2);
			
			if(k1+bandwidth<=K+1e-6){
				Q.insert(mk(t0-vol/bandwidth,-bandwidth));
				reassign(p,2,p->se+bandwidth);
				break;
			}
			else
			if(vol<vol1){
				Q.insert(mk(t0-vol/(K-k1),-(K-k1)));
				reassign(p,2,K);
				break;
			}
			else
			if(k2+bandwidth>=K){
				if(vol<=vol2){
					double t=q->fi-(vol-vol1)/(K-k2);
					reassign(p,2,K);
					Q.erase(q); Q.insert(mk(t,-(K-k2)));
					break;
				}
				else goto merge;
			}else
			{
				double l1=t0-vol/bandwidth,
					   l2=q->fi-Get_len(q),
					   l=t0-volp/(K-bandwidth-k2);
				if(l>max(l1,l2)){
					reassign(p,2,K-bandwidth);
					reassign(q,1,l);
					continue;
				}else if(l2>l1){
					goto merge;
				}else{
					vol+=volp;
					bandwidth=min((double)K,bandwidth+volp/(t0-l1));
					Q.erase(p);
					Q.erase(q);
					Q.insert(mk(t0,k2));
				}
			}
			continue;
			merge:;
			double delta=volp/(Get_len(p)+Get_len(q));
			It tmp=q; tmp--;
			Q.erase(p);
			Q.erase(q);
			reassign(tmp,2,tmp->se-delta);
			Q.insert(mk(t0,k2+delta));
		}
		//for(auto x:Q)printf("%lf %lf\n",x.fi,x.se);puts("\n========");
	}
	It p=Q.begin();p++;p++;
	printf("%lf\n",c[n]-p->fi);
	//for(;;);
}