Advertisement
tsypko

Untitled

Aug 25th, 2017
124
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.52 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. inline void read(int &n) {
  6.     char c;
  7.     n = 0;
  8.     while (true) {
  9.         c = getchar();
  10.         if (c == ' ' || c == '\n') {
  11.             break;
  12.         }
  13.         n = n * 10 + (c - '0');
  14.     }
  15. }
  16.  
  17. const int MAX = 1505;
  18.  
  19. int ar[MAX][MAX];
  20.  
  21. int dp[MAX][MAX];
  22.  
  23. struct t {
  24.     int a, b, c, d;
  25.     t() {
  26.         a = b = c = d = 0;
  27.     }
  28.     void add(int g) {
  29.         if (g > d) {
  30.             d = g;
  31.             if (d > c) {
  32.                 swap(c, d);
  33.                 if (c > b) {
  34.                     swap(b, c);
  35.                     if (a < b) {
  36.                         swap(a, b);
  37.                     }
  38.                 }
  39.             }
  40.         }
  41.     }
  42.     inline int get(int x = 0, int y = 0, int z = 0) {
  43.         if (a == x || a == y || a == z) {
  44.             if (a == x) {
  45.                 x = 0;
  46.             } else if (a == y) {
  47.                 y = 0;
  48.             } else {
  49.                 z = 0;
  50.             }
  51.             if (b == x || b == y || b == z) {
  52.                 if (b == x) {
  53.                     x = 0;
  54.                 } else if (b == y) {
  55.                     y = 0;
  56.                 } else {
  57.                     z = 0;
  58.                 }
  59.                 if (c == x || c == y || c == z) {
  60.                     return d;
  61.                 } else {
  62.                     return c;
  63.                 }
  64.             } else {
  65.                 return b;
  66.             }
  67.         } else {
  68.             return a;
  69.         }
  70.     }
  71. };
  72.  
  73. t t1[MAX], t2[MAX];
  74.  
  75. vector<pair<int, int> > v[MAX * MAX];
  76.  
  77. int n;
  78.  
  79. #define ar dp
  80. int get(int x, int y) {
  81.     int ans = 0;
  82.     if (x > 1) {
  83.         ans = max(ans, t1[x - 1].get(ar[x - 1][y - 1], ar[x - 1][y],
  84.         ar[x - 1][y + 1]));
  85.     }
  86.     if (x < n) {
  87.         ans = max(ans, t1[x + 1].get(ar[x + 1][y - 1], ar[x + 1][y],
  88.         ar[x + 1][y + 1]));
  89.     }
  90.     if (y > 1) {
  91.         ans = max(ans, t2[y - 1].get(ar[x - 1][y - 1], ar[x][y - 1],
  92.         ar[x + 1][y - 1]));
  93.     }
  94.     if (y < n) {
  95.         ans = max(ans, t2[y + 1].get(ar[x - 1][y + 1], ar[x][y + 1],
  96.         ar[x + 1][y + 1]));
  97.     }
  98.     return ans;
  99. }
  100. #undef ar
  101.  
  102. int main(int argc, char **argv) {
  103. #ifdef LOCAL
  104.     freopen("input.txt", "r", stdin);
  105. #endif
  106.     int x, y;
  107.     read(n);
  108.     read(x);
  109.     read(y);
  110.     for (int i = 1; i <= n; i++) {
  111.         for (int j = 1; j <= n; j++) {
  112.             read(ar[i][j]);
  113.             v[ar[i][j]].push_back(make_pair(i, j));
  114.         }
  115.     }
  116.     dp[x][y] = 1;
  117.     t1[x].add(1);
  118.     t2[y].add(1);
  119.     int ans = 1;
  120.     vector<int> vv;
  121.     for (int j = ar[x][y] + 1; j < MAX * MAX; j++) {
  122.         vv.clear();
  123.         for (pair<int, int> a : v[j]) {
  124.             int res = get(a.first, a.second);
  125.             if (res) {
  126.                 res++;
  127.                 vv.push_back(res);
  128.                 ans = max(ans, res);
  129.             }else{
  130.                 vv.push_back(0);
  131.             }
  132.             //cout << a.first << " " << a.second << " " << ar[a.first][a.second] << " " << vv.back() << endl;
  133.         }
  134.         reverse(vv.begin(), vv.end());
  135.         for (pair<int, int> a : v[j]) {
  136.             int res = dp[a.first][a.second] = vv.back();
  137.             vv.pop_back();
  138.             t1[a.first].add(res);
  139.             t2[a.second].add(res);
  140.         }
  141.     }
  142.     cout << ans << endl;
  143. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement