Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- inline void read(int &n) {
- char c;
- n = 0;
- while (true) {
- c = getchar();
- if (c == ' ' || c == '\n') {
- break;
- }
- n = n * 10 + (c - '0');
- }
- }
- const int MAX = 1505;
- int ar[MAX][MAX];
- int dp[MAX][MAX];
- struct t {
- int a, b, c, d;
- t() {
- a = b = c = d = 0;
- }
- void add(int g) {
- if (g > d) {
- d = g;
- if (d > c) {
- swap(c, d);
- if (c > b) {
- swap(b, c);
- if (a < b) {
- swap(a, b);
- }
- }
- }
- }
- }
- inline int get(int x = 0, int y = 0, int z = 0) {
- if (a == x || a == y || a == z) {
- if (a == x) {
- x = 0;
- } else if (a == y) {
- y = 0;
- } else {
- z = 0;
- }
- if (b == x || b == y || b == z) {
- if (b == x) {
- x = 0;
- } else if (b == y) {
- y = 0;
- } else {
- z = 0;
- }
- if (c == x || c == y || c == z) {
- return d;
- } else {
- return c;
- }
- } else {
- return b;
- }
- } else {
- return a;
- }
- }
- };
- t t1[MAX], t2[MAX];
- vector<pair<int, int> > v[MAX * MAX];
- int n;
- #define ar dp
- int get(int x, int y) {
- int ans = 0;
- if (x > 1) {
- ans = max(ans, t1[x - 1].get(ar[x - 1][y - 1], ar[x - 1][y],
- ar[x - 1][y + 1]));
- }
- if (x < n) {
- ans = max(ans, t1[x + 1].get(ar[x + 1][y - 1], ar[x + 1][y],
- ar[x + 1][y + 1]));
- }
- if (y > 1) {
- ans = max(ans, t2[y - 1].get(ar[x - 1][y - 1], ar[x][y - 1],
- ar[x + 1][y - 1]));
- }
- if (y < n) {
- ans = max(ans, t2[y + 1].get(ar[x - 1][y + 1], ar[x][y + 1],
- ar[x + 1][y + 1]));
- }
- return ans;
- }
- #undef ar
- int main(int argc, char **argv) {
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- #endif
- int x, y;
- read(n);
- read(x);
- read(y);
- for (int i = 1; i <= n; i++) {
- for (int j = 1; j <= n; j++) {
- read(ar[i][j]);
- v[ar[i][j]].push_back(make_pair(i, j));
- }
- }
- dp[x][y] = 1;
- t1[x].add(1);
- t2[y].add(1);
- int ans = 1;
- vector<int> vv;
- for (int j = ar[x][y] + 1; j < MAX * MAX; j++) {
- vv.clear();
- for (pair<int, int> a : v[j]) {
- int res = get(a.first, a.second);
- if (res) {
- res++;
- vv.push_back(res);
- ans = max(ans, res);
- }else{
- vv.push_back(0);
- }
- //cout << a.first << " " << a.second << " " << ar[a.first][a.second] << " " << vv.back() << endl;
- }
- reverse(vv.begin(), vv.end());
- for (pair<int, int> a : v[j]) {
- int res = dp[a.first][a.second] = vv.back();
- vv.pop_back();
- t1[a.first].add(res);
- t2[a.second].add(res);
- }
- }
- cout << ans << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement