Cod sursa(job #3359519)

Utilizator rares89_Dumitriu Rares rares89_ Data 29 iunie 2026 13:30:44
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");

int n, m;
vector<vector<int>> a, rad;
long long ans;

int main() {
    fin >> n >> m;

    a.resize(n, vector<int>(m));
    rad.resize(n, vector<int>(m));

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

    for (int i = 0; i < n; ++i) {
        int l = 0, r = -1;

        for (int j = 0; j < m; ++j) {
            int k = 1;

            if (j <= r)
                k = min(rad[i][l + r - j], r - j + 1);

            while (j - k >= 0 && j + k < m && a[i][j - k] == a[i][j + k])
                ++k;

            rad[i][j] = k;

            if (j + k - 1 > r) {
                l = j - k + 1;
                r = j + k - 1;
            }
        }
    }

    for (int col = 0; col < m; ++col) {
        stack<int> st;

        for (int i = 0; i <= n; ++i) {
            int val = 0;

            if (i < n)
                val = rad[i][col];

            while (!st.empty() && rad[st.top()][col] >= val) {
                int h = rad[st.top()][col];
                st.pop();

                int last = -1;

                if (!st.empty())
                    last = st.top();

                int lines = i - last - 1;
                ans = max(ans, 1LL * lines * (2 * h - 1));
            }

            st.push(i);
        }
    }

    fout << ans << "\n";

    return 0;
}