记录编号	159957	评测结果	AAAAAAAAAAAAAA
题目名称	1948.奶牛跑步2	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.306 s
提交时间	2015-04-23 13:24:00	内存使用	2.96 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
int n,r[100010],ans=0;
long long t,end[100010],f[100010]={0};
class miku
{
public:
	int id;
	int sp;
}cow[100010];
int cmp(long long a,long long b)
{
	return a>b;
}
int main()
{
	freopen("cowjogb.in","r",stdin);
	freopen("cowjogb.out","w",stdout);
	scanf("%d%lld",&n,&t);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&cow[i].id,&cow[i].sp);
		end[i]=cow[i].id+cow[i].sp*t;
	}
	f[0]=2e18;
	int len=0;
	for(int i=1;i<=n;i++)
	{
		int k=upper_bound(f,f+len+1,end[i],cmp)-f;
		if(k>len) len=k;
		f[k]=end[i];
	}
	printf("%d",len);
	return 0;
}