Cod sursa(job #1939937)

Utilizator lflorin29Florin Laiu lflorin29 Data 26 martie 2017 10:51:40
Problema DreptPal Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <bits/stdc++.h>

using namespace std;

const int nMax = 1002;

int n, m, a[nMax][nMax];
int dp[nMax][nMax];
int st[nMax], dr[nMax];

int main() {
    ifstream fin("dreptpal.in");
    ofstream fout("dreptpal.out");
    fin >> n >> m;

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            fin >> a[j][i];

    swap(n, m);

    for (int i = 1; i <= m; ++i) {
        int c = 0;

        for (int j = 1; j <= n; ++j) {
            dp[j][i] = max(1, min(dp[c][i] + c - j, dp[2 * c - j][i]));

            int &nr = dp[j][i];

            while (j + nr <= n && j - nr >= 1 && a[j + nr][i] == a[j - nr][i])
                ++nr;

            if (j + dp[j][i] > c + dp[c][j])
                c = j;

        }
    }


    stack<int>s;
    int ans = 0;

    for (int i = 1; i <= n; ++i) {

        for (int j = 1; j <= m; ++j) {
            st[j] = j;
            dr[j] = j;
        }

        s = stack<int>();

        for (int j = 1; j <= m; ++j) {
            while (!s.empty() && dp[i][s.top()] >= dp[i][j])
                s.pop();

            if (s.empty())
                st[j] = 1;
            else st[j] = s.top() + 1;

            s.push(j);
        }

        s = stack<int>();

        for (int j = m; j; --j) {
            while (!s.empty() && dp[i][s.top()] >= dp[i][j])
                s.pop();

            if (s.empty())dr[j] = m;
            else dr[j] = s.top() - 1;

            s.push(j);
        }

        for (int j = 1; j <= m; ++j) {
            int dif = (dr[j] - st[j] + 1);

            int v = dif * (2 * dp[i][j] - 1);
            ans = max(ans, v);
        }
    }

    fout << ans;
    return 0;
}