记录编号	353207	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	水站	最终得分	100
用户昵称	kito	是否通过	通过
代码语言	C++	运行时间	0.097 s
提交时间	2016-11-17 20:56:33	内存使用	0.58 MiB

#include<cstdio>
#include<cstring>
using namespace std;
#define	fcl	fclose(stdin);	fclose(stdout);	return 0
	#define SUBMIT 2333
int n;
int w[15010],L[15010],P[15010],sum[15010];
int cost[15010];
int Find(int a){
	int l=1,r=a,mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(sum[a]-sum[mid-1]>L[a])	l=mid+1;
		else r=mid-1;
	}
	return l;
}

int main(){
	#ifdef SUBMIT
	freopen("station.in","r",stdin);
	freopen("station.out","w",stdout);
	#endif
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d%d%d",&w[i],&L[i],&P[i]);
		sum[i]=sum[i-1]+w[i];
	}
	int x;
	for(int i=1;i<=n;++i){
		x=Find(i);
		cost[x]+=P[i];
		cost[i+1]-=P[i];
	}
	int ans=0x7f7f7f7f,k;
	for(int i=1;i<=n;++i){
		cost[i]+=cost[i-1];
		if(cost[i]<ans){
			ans=cost[i];
			k=i;
		}
	}
	printf("%d\n",ans);
	for(int i=k;i<=n;++i){
		if(sum[i]-sum[k-1]<=L[i])	printf("%d ",i);
	}
	#ifndef SUBMIT
	getchar();	getchar();
	#endif
	fcl;
}