Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define sz(x) int(x.size())
- #define all(x) x.begin(),x.end()
- #define reset(x) memset(x, 0,sizeof(x))
- #define pb push_back
- #define mp make_pair
- #define fi first
- #define se second
- #define N 105
- #define remain(x) if (x > MOD) x -= MOD
- #define ii pair<int, int>
- #define iiii pair< ii , ii >
- #define viiii vector< iiii >
- #define vi vector<int>
- #define vii vector< ii >
- #define bit(x, i) (((x) >> (i)) & 1)
- #define Task "grab"
- #define int long long
- using namespace std;
- typedef long double ld;
- const int inf = 1e10;
- const int minf = -1e10;
- int n;
- int a[N][N];
- int dp[N][N];
- ii trace[N][N];
- int ic, jc;
- void readfile()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);cout.tie(0);
- if (fopen(Task".inp","r"))
- {
- freopen(Task".inp","r",stdin);
- freopen(Task".out","w",stdout);
- }
- cin >> n;
- memset(a, 0, sizeof a);
- int x, y;
- while (cin >> x >> y)
- {
- a[x][y] = 1;
- }
- }
- void traceback()
- {
- stack<ii> st;
- ii s = ii(ic,jc);
- while (s != ii(0,0))
- {
- st.push(s);
- s = trace[s.fi][s.se];
- }
- while (st.size())
- {
- cout << st.top().fi << ' ' << st.top().se << endl;
- st.pop();
- }
- }
- void proc()
- {
- for(int i=1; i<=n; i++)
- {
- for(int j=1; j<=n; j++)
- {
- if (a[i][j]==0) dp[i][j] = 0;
- else{
- for(int u = 0; u < i; u++)
- {
- for(int v=0; v < j; v++)
- {
- if (dp[i][j] < dp[u][v] + 1)
- {
- dp[i][j] = dp[u][v]+1;
- trace[i][j] = ii(u,v);
- }
- }
- }
- }
- }
- }
- int ans = 0;
- for(int i=1; i<=n; i++)
- {
- for(int j=1; j<=n; j++)
- {
- if (dp[i][j] > ans)
- {
- ans = dp[i][j];
- ic = i;
- jc = j;
- }
- }
- }
- cout << ans << endl;
- traceback();
- }
- signed main()
- {
- readfile();
- proc();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement