记录编号	232729	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	水站	最终得分	100
用户昵称	NVIDIA	是否通过	通过
代码语言	C++	运行时间	0.119 s
提交时间	2016-03-02 19:55:49	内存使用	1.00 MiB

#include<fstream>
using namespace std;
class xx{
public:
	int x,y;
};
ifstream fin("station.in");
ofstream fout("station.out");
xx t,a[30000];
int p[30000],l[30000],w[30000],sum[30000];
bool done;
int n,tot,cost,m,k;
void up(int i){
	done=false;
	if (i==1) return;
	while (i!=1&&!done){
		if (a[i].x>a[i/2].x){
			t=a[i];
			a[i]=a[i/2];
			a[i/2]=t;
		}
		else
			done=true;
		i=i/2;
	}
}
void down(int i){
	cost=cost-a[1].y;
	a[1].x=-1000000000;
	done=false;
	if (i*2>tot) return;
	while(2*i<=tot&&!done){
		i=i*2;
		if (i+1<=tot&&a[i+1].x>a[i].x)
			i++;
		if (a[i/2].x<a[i].x){
			t=a[i/2];
			a[i/2]=a[i];
			a[i]=t;
		}
		else
			done=true;
	}
}
int main(){
	fin>>n;
for(int i=1;i<=n;i++){
fin>>w[i]>>l[i]>>p[i];
sum[i]=sum[i-1]+w[i];
}
tot=1;
a[1].x=sum[n]-l[n];
a[1].y=p[n];
if (w[n]>l[n])
	a[1].y=0;
cost=a[1].y;
m=cost;
for(int i=n-1;i>0;i--){
	while (a[1].x>sum[i-1])
		down(1);
	tot++;
	a[tot].x=sum[i]-l[i];
	a[tot].y=p[i];
	if (w[i]>l[i])
		a[tot].y=0;
	else
		cost=cost+p[i];
	up(tot);
	if (cost<m){
		m=cost;
		k=i;
	}
}

fout<<m<<endl;
fout<<k<<' ';
for(int i=k+1;i<=n;i++)
	if (sum[i]-sum[k-1]<=l[i])
		fout<<i<<' ';
	return 0;
}