比赛 20150423 评测结果 AWWWWWWWWWWWWW
题目名称 奶牛跑步2 最终得分 7
用户昵称 slyrabbit 运行时间 1.044 s
代码语言 C++ 内存使用 2.99 MiB
提交时间 2015-04-23 09:01:08
显示代码纯文本
  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. class cow
  5. {
  6. public:
  7. int p;
  8. long long rank;
  9. long long place;
  10. long long v;
  11. cow(){
  12. p=0;rank=0;place=0;v=0;
  13. }
  14. }a[100005];
  15. int n,t;
  16. //*************************************不要浮躁***************************************//
  17. int find(int x)
  18. {
  19. if(x!=a[x].p)
  20. return a[x].p=find(a[x].p);
  21. return a[x].p;
  22. }
  23. void link(int x,int y)
  24. {
  25. a[x].p=y;
  26. }
  27. void a_union(int x,int y)
  28. {
  29. link(find(x),find(y));
  30. }
  31. void init()
  32. {
  33. cin>>n>>t;
  34. for(int i=1;i<=n;i++)
  35. {
  36. a[i].p=i;
  37. cin>>a[i].place>>a[i].v;
  38. a[i].rank=a[i].place+a[i].v*t;
  39. }
  40. }
  41. void work()
  42. {
  43. int count[100005]={0};
  44. int Max=0;
  45. for(int i=n;i>1;i--)
  46. {
  47. if(a[i-1].rank>=a[i].rank)
  48. a_union(i-1,i);
  49. }
  50. for(int i=1;i<=n;i++) count[find(i)]++;
  51. for(int i=1;i<=n;i++) if(count[i]>Max) Max=count[i];
  52. cout<<Max;
  53. }
  54. int main()
  55. {
  56. freopen("cowjogb.in","r",stdin);
  57. freopen("cowjogb.out","w",stdout);
  58. init();
  59. work();
  60. return 0;
  61. }