fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 3e4 + 1;
  4.  
  5. int n , dp[N];
  6. vector < int > e[N];
  7.  
  8. int recur ( int time ){
  9.  
  10.    if ( time >= N ) return 0;
  11.  
  12.    int &ret = dp[time];
  13.  
  14.    if ( ~ret ) return ret;
  15.  
  16.    ret = recur ( time + 1 );
  17.  
  18.    for ( auto child : e[time] ){
  19.      ret = max ( ret , 1 + recur ( child + 1 ) );
  20.    }
  21.  
  22.    return ret;
  23. }
  24.  
  25. void Solution ( int tc ){
  26.  
  27.   cin >> n;
  28.  
  29.   for ( int i = 1 ; i <= n ; i++ ){
  30.     int st;
  31.     int en;
  32.     cin >> st >> en;
  33.     e[st].push_back ( en );
  34.   }
  35.  
  36.   cout << recur ( 1 ) << "\n";
  37.  
  38.   return;
  39. }
  40.  
  41. int main()
  42. {
  43.     /// MUHAMMAD
  44.     ios::sync_with_stdio(0);
  45.     cin.tie(0);
  46.  
  47.     /// AE;
  48.  
  49.     /*
  50.     #ifdef OJ
  51.         freopen("input.txt", "r", stdin);
  52.         freopen("output.txt", "w", stdout);
  53.     #endif
  54.     */
  55.  
  56.     int testcase = 1 , tc = 0;
  57.  
  58.     for ( int i = 0 ; i < N ; ++i ){
  59.         dp[i] = -1;
  60.     }
  61.  
  62.     /// cin >> testcase;
  63.  
  64.     for ( int i = 1 ; i <= testcase ; ++i ){
  65.        Solution( ++tc );
  66.     }
  67.  
  68.     return 0;
  69. }
  70.  
Success #stdin #stdout 0.01s 5872KB
comments (?)
stdin
copy 
1
1 30
stdout
copy 
1
https://ideone.com/XYTrQG
language:
C++ (gcc 8.3)
created:
3 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!