fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main(){
  5. ios_base::sync_with_stdio(false);
  6. int i,j,k,n,m,a,b,c;
  7. cin>>n;
  8. vector<int> x(n),h(n);
  9. for(i=0;i<n;i++){
  10.     cin>>x[i]>>h[i];
  11. }
  12. int arr[n][3];  //0=lft,1=st,2=ri
  13. memset(arr,0,sizeof(arr));
  14. /*for(i=0;i<3;i++)
  15.     arr[0][i]=1;    */
  16.     arr[0][0]=1;
  17.     arr[0][1]=0;
  18.     arr[0][2]=0;
  19.  
  20. for(i=1;i<n;i++){
  21.     if(x[i-1]+h[i]<x[i])
  22.         arr[i][0]=max(arr[i-1][0],arr[i-1][1])+1;
  23.     arr[i][1]=max({arr[i-1][0],arr[i-1][2],arr[i-1][1]});
  24.     if(i+1<n && x[i]+h[i]<x[i+1])
  25.         arr[i][2]=max({arr[i-1][0],arr[i-1][1],arr[i-1][2]})+1;
  26. }
  27. if(n-2>=0)
  28. arr[n-1][2]=max({arr[n-2][0],arr[n-2][1],arr[n-2][2]})+1;
  29. cout<<max({arr[n-1][0],arr[n-1][1],arr[n-1][2]})<<"\n";
  30. /*for(i=0;i<3;i++, cout<<"\n"){
  31.     for(j=0;j<n;j++)
  32.         cout<<arr[j][i]<<" ";
  33. }*/
  34.  
  35. return 0;
  36. }
  37.  
Success #stdin #stdout 0s 15496KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2
https://ideone.com/f3wbBy
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!