Advertisement
MinhNGUYEN2k4

ge

Mar 30th, 2021
232
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.18 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define sz(x) int(x.size())
  3. #define all(x) x.begin(),x.end()
  4. #define reset(x) memset(x, 0,sizeof(x))
  5. #define pb push_back
  6. #define mp make_pair
  7. #define fi first
  8. #define se second
  9. #define N 105
  10. #define remain(x) if (x > MOD) x -= MOD
  11. #define ii pair<int, int>
  12. #define iiii pair< ii , ii >
  13. #define viiii vector< iiii >
  14. #define vi vector<int>
  15. #define vii vector< ii >
  16. #define bit(x, i) (((x) >> (i)) & 1)
  17. #define Task "grab"
  18. #define int long long
  19.  
  20. using namespace std;
  21.  
  22. typedef long double ld;
  23. const int inf = 1e10;
  24. const int minf = -1e10;
  25.  
  26. int n;
  27. int a[N][N];
  28. int dp[N][N];
  29. ii trace[N][N];
  30. int ic, jc;
  31.  
  32. void readfile()
  33. {
  34.     ios_base::sync_with_stdio(false);
  35.     cin.tie(0);cout.tie(0);
  36.     if (fopen(Task".inp","r"))
  37.     {
  38.         freopen(Task".inp","r",stdin);
  39.         freopen(Task".out","w",stdout);
  40.     }
  41.     cin >> n;
  42.     memset(a, 0, sizeof a);
  43.     int x, y;
  44.     while (cin >> x >> y)
  45.     {
  46.         a[x][y] = 1;
  47.     }
  48. }
  49.  
  50. void traceback()
  51. {
  52.     stack<ii> st;
  53.     ii s = ii(ic,jc);
  54.     while (s != ii(0,0))
  55.     {
  56.         st.push(s);
  57.         s = trace[s.fi][s.se];
  58.     }
  59.     while (st.size())
  60.     {
  61.         cout << st.top().fi << ' ' << st.top().se << endl;
  62.         st.pop();
  63.     }
  64. }
  65.  
  66. void proc()
  67. {
  68.     for(int i=1; i<=n; i++)
  69.     {
  70.         for(int j=1; j<=n; j++)
  71.         {
  72.             if (a[i][j]==0) dp[i][j] = 0;
  73.             else{
  74.                 for(int u = 0; u < i; u++)
  75.                 {
  76.                     for(int v=0; v < j; v++)
  77.                     {
  78.                         if (dp[i][j] < dp[u][v] + 1)
  79.                         {
  80.                             dp[i][j] = dp[u][v]+1;
  81.                             trace[i][j] = ii(u,v);
  82.                         }
  83.                     }
  84.                 }
  85.             }
  86.         }
  87.     }
  88.     int ans = 0;
  89.     for(int i=1; i<=n; i++)
  90.     {
  91.         for(int j=1; j<=n; j++)
  92.         {
  93.             if (dp[i][j] > ans)
  94.             {
  95.                 ans = dp[i][j];
  96.                 ic = i;
  97.                 jc = j;
  98.             }
  99.         }
  100.     }
  101.     cout << ans << endl;
  102.     traceback();
  103. }
  104.  
  105. signed main()
  106. {
  107.     readfile();
  108.     proc();
  109.     return 0;
  110. }
  111.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement