记录编号	27954	评测结果	AATTAAAWAT
题目名称	垃圾陷阱	最终得分	60
用户昵称	Truth.Cirno	是否通过	未通过
代码语言	C++	运行时间	4.021 s
提交时间	2011-10-10 20:18:36	内存使用	0.26 MiB

#include <cstdio>
using namespace std;

int deep,n,tim[101],hp[101],hei[101],heimax=0,mintime=2000/*,hpmax=0,hpnow=10,heinow=0*/;

void swap(int &a,int &b)
{
	int temp;
	temp=a;
	a=b;
	b=temp;
}

void qqsort(int l,int r)
{
	int ll,rr,temp;
	ll=l;
	rr=r;
	temp=tim[(l+r)/2];
	while (ll<=rr)
	{
		while (tim[ll]<temp)
			ll++;
		while (tim[rr]>temp)
			rr--;
		if (ll<=rr)
		{
			swap(tim[ll],tim[rr]);
			swap(hp[ll],hp[rr]);
			swap(hei[ll],hei[rr]);
			ll++;
			rr--;
		}
	}
	if (l<rr)
		qqsort(l,rr);
	if (ll<r)
		qqsort(ll,r);
}

void tryit(int now,bool eat,int hpnow,int heinow,int rest)
{
	if (eat)
	{
		hpnow+=hp[now];
		rest-=hei[now];
	}
	else
		heinow+=hei[now];
	if (now>n)
		return;
	if (tim[now]>hpnow)
		return;
	if (mintime<=tim[now])
		return;
	if (rest<deep)
		return;
	if (deep<=heinow)
//	{
		mintime=tim[now];
//	}
	else
	{
//		if (eat)
//		{
//			tryit(now+1,0,hpnow,heinow,rest);
//			tryit(now+1,1,hpnow,heinow,rest);
//		}
//		else
//		{
			tryit(now+1,0,hpnow,heinow,rest);
			tryit(now+1,1,hpnow,heinow,rest);
//		}
	}
}

int main(void)
{
	freopen("well.in","r",stdin);
	freopen("well.out","w",stdout);
	int i;
	scanf("%d %d",&deep,&n);
	for (i=1;i<=n;i++)
	{
		scanf("%d %d %d",&tim[i],&hp[i],&hei[i]);
//		hpmax+=hp[i];
		heimax+=hei[i];
	}
	qqsort(1,n);
	tryit(1,0,10,0,heimax);
	tryit(1,1,10,0,heimax);
	if (mintime!=2000)
		printf("%d\n",mintime);
	else
	{
		int hpnow=10;
		for (i=1;i<=n;i++)
//		{
			if (tim[i]<=hpnow)
				hpnow+=hp[i];
			else
				break;
//		}
		printf("%d\n",hpnow);
	}
	fclose(stdin);
	fclose(stdout);
	return(0);
}