记录编号 353207 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 水站 最终得分 100
用户昵称 Gravatarkito 是否通过 通过
代码语言 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;
}