记录编号	352552	评测结果	AAAAAAAAAA
题目名称	尼克的任务	最终得分	100
用户昵称	Zwoi_只会打表抄代码的蒟蒻	是否通过	通过
代码语言	C	运行时间	0.014 s
提交时间	2016-11-17 12:18:05	内存使用	0.48 MiB

#include <stdio.h>
#include <stdlib.h>
typedef struct tree
{
	int s,t;
}AAA;
AAA a[10010],book[10010];
int n,m,i,k[10010],max,j;
int cmp(const void *a,const void *b)
{return (*(AAA*)a).s>(*(AAA*)b).s?1:-1;}
int main()
{
	freopen("lignja.in","r",stdin);
	freopen("lignja.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
		scanf("%d%d",&a[i].s,&a[i].t);
	qsort(a+1,m,sizeof(a[0]),cmp);
	k[n+1]=0;
	for(i=1;i<=m;i++)
	{
		book[a[i].s].s++;
		book[a[i].s].t=i;
	}
	for(i=n;i>0;i--)
	{
		if(book[i].s)
		{
			max=0;
			for(j=book[i].t;j>book[i].t-book[i].s;j--)
				if(k[a[j].s+a[j].t]>max)
					max=k[a[j].s+a[j].t];
			k[i]=max;
		}
		else
			k[i]=k[i+1]+1;			
	}
	printf("%d",k[1]);
	return 0;
}