记录编号	27746	评测结果	AWAWAWWAWA
题目名称	垃圾陷阱	最终得分	50
用户昵称	苏轼	是否通过	未通过
代码语言	C++	运行时间	0.004 s
提交时间	2011-09-29 11:12:53	内存使用	0.27 MiB

#include<iostream>
#include<stdio.h>//freopen
#include<string.h>//?????????
#include<cstdlib>//?????????
#include<stdlib.h>//????????
#include<cstdlib>
#include<cstdio>
using namespace std;
int cmp(const void *a,const void *b);
int MAX=0;
int q[102];
int number,longth;//???????
struct hehe
{
	int t,h,l;//??????????????
}a[200];
void dp();//DP
int main()
{
	freopen ("well.in","r",stdin);
	freopen ("well.out","w",stdout);
	scanf("%d %d",&longth,&number);
	for (int i=0;i<number;i++)
	{
		scanf("%d %d %d\n",&a[i].t,&a[i].h,&a[i].l);
		MAX+=a[i].h;//????????????Β?о?ü?0
	}
	MAX+=10;
	qsort(&a[0],number,sizeof(a[0]),cmp);//???????????С??????
	int answer=0;//?Ξ???????
	q[0]=10;
	for (int i=0;i<number;i++)
	{
		answer=0;
        for(int j=longth; j>=0; j--)
		{
            if(q[j] >= a[i].t) 
			{
                if(j + a[i].l >= longth) 
				{
                    printf("%d\n", a[i].t);
					goto end;
                }
                if(q[j] > q[j+a[i].l])
                    q[j+a[i].l] = q[j];
                q[j] += a[i].h;
                answer = 1;
            }
        }
        if(!answer)
            break;
	}
	if (!answer)//????????????
	{
		int ji=10;//????10??P??
		for (int i=0;i<number;i++)
		{
			if (ji-a[i].l)//??????????????
			{
				ji=ji-a[i].l+a[i].h;
			}
		}
		cout<<ji;
	}
end:
	return 0;
}
int cmp(const void *a,const void *b)
{
	return ((hehe *)a)->t > ((hehe *)b)->t ? 1 : -1;//???????
}