fork download
  1. #include <iostream>
  2. #include <set>
  3. #include <algorithm>
  4. #include <string.h>
  5. using namespace std;
  6. //堀江 aoj693 Event Hopping
  7. long long int dp[200010][2][2];
  8. std::set<long long int> ss[2];
  9.  
  10. int main() {
  11. long long int n,d,k1;
  12. cin>>n>>d>>k1;
  13. for(int i=0;i<n;i++){
  14. long long int s1,t1;
  15. cin>>s1>>t1;
  16. ss[s1-1].insert(t1);
  17. }
  18. memset(dp,-1,sizeof(dp));
  19. dp[0][0][0]=0;
  20. dp[0][1][0]=0;
  21. dp[0][0][1]=0;
  22. dp[0][1][1]=0;
  23. int ans=0;
  24. for(int i=0;i<=n;i++){
  25. for(int j=0;j<2;j++){
  26. for(int k=0;k<2;k++){
  27. long long int t0=dp[i][k][j];
  28. if(t0==-1)continue;
  29. long long int t1=0;
  30. if(j==k){
  31. t1=t0;
  32. }else{
  33. t1=t0+d+i*k1;
  34. }
  35. auto it=ss[k].lower_bound(t1);
  36. if(it==ss[k].end()){
  37. if(ans<i)ans=i;
  38. }else{
  39. long long int ta,tb;
  40. ta=dp[i+1][0][k];
  41. tb=dp[i+1][1][k];
  42. if(ta==-1 || (*it)+1<ta)dp[i+1][0][k]=(*it)+1;
  43. if(tb==-1 || (*it)+1<tb)dp[i+1][1][k]=(*it)+1;
  44. }
  45. //cout<<"("<<t1<<" "<<k<<","<<j<<","<<dp[i][k][j]<<")";
  46. }
  47. }
  48. //cout<<endl;
  49. }
  50. cout<<ans<<endl;
  51. return 0;
  52. }
Success #stdin #stdout 0.01s 9800KB
stdin
15 89 104
1 4379
1 738
1 4862
1 4236
2 1416
1 9905
1 4775
2 4574
2 439
1 3956
1 955
2 8862
2 801
2 2299
2 575
stdout
11