比赛 |
20150423 |
评测结果 |
AAAAAAAAAAAAAA |
题目名称 |
奶牛跑步2 |
最终得分 |
100 |
用户昵称 |
cstdio |
运行时间 |
0.370 s |
代码语言 |
C++ |
内存使用 |
3.36 MiB |
提交时间 |
2015-04-23 08:55:34 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iomanip>
#include<cstdlib>
using namespace std;
typedef long long LL;
const int SIZEN=100010;
int N;
LL T;
LL pos[SIZEN],vel[SIZEN],end[SIZEN];
//要把序列拆成若干个严格递增序列
//求最长的非严格单调减序列的长度
LL f[SIZEN]={0};
bool cmp(const LL &a,const LL &b){return a>b;}
void work(void){
int len=0;
f[0]=2e18;
for(int i=1;i<=N;i++){
int k=upper_bound(f,f+len+1,end[i],cmp)-f;
//for(int i=0;i<=len;i++) cout<<f[i]<<" ";cout<<endl<<end[i]<<" "<<k<<endl<<endl;
if(k>len) len=k;
f[k]=end[i];
}
printf("%d\n",len);
}
void init(void){
scanf("%d",&N);
scanf("%lld",&T);
for(int i=1;i<=N;i++){
scanf("%lld %lld",&pos[i],&vel[i]);
end[i]=pos[i]+T*vel[i];
}
//for(int i=1;i<=N;i++) cout<<end[i]<<" ";cout<<endl<<endl;
}
int main(){
freopen("cowjogb.in","r",stdin);
freopen("cowjogb.out","w",stdout);
init();
work();
return 0;
}