Cod sursa(job #2306415)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 22 decembrie 2018 12:09:00
Problema DreptPal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

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

void compute(vector<int> &dist, const vector<int> &v, int start, int n, int add) {
    vector<int> stk(n + 1, 0);
    int sz = 0;
    dist[start] = 1;
    stk[++sz] = start;

    for(int i = start + add; i <= n && i >= 1; i += add) {
        while(sz && v[i] <= v[stk[sz]])
            sz --;
        dist[i] = abs(i - stk[sz]);
        stk[++sz] = i;
    }
}

int solve(const vector<int> &v, int n) {
    vector<int> distoleft(n + 1, 0);
    compute(distoleft, v, 1, n, 1);

    vector<int> distoright(n + 1, 0);
    compute(distoright, v, n, n, -1);

    int ans = 0;
    for(int i = 1; i <= n; i ++)
        ans = max(ans, (distoright[i] + distoleft[i] - 1) * v[i]);

    return ans;

}

int main() {

    int n, m;
    in >> n >> m;
    vector<vector<int>> v(n + 1, vector<int> (m + 1, 0));
    vector<vector<int>> palmax(m + 2, vector<int> (n + 2, 1));
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= m; j ++)
            in >> v[i][j];

        vector<int> p(m + 1, 0);
        int r = 1, pos = 1;
        p[1] = 1;

        for(int j = 2; j <= m; j ++) {
            if(r > j)
                p[j] = min(r - j + 1, p[2 * pos - j]);
            else
                p[j] = 1;

            while(0 < j - p[j] && j + p[j] <= m && v[i][j - p[j]] == v[i][j + p[j]])
                p[j] ++;

            if(j + p[j] - 1 > r) {
                r = j + p[j] - 1;
                pos = j;
            }

            if(r >= j)
                palmax[j][i] = (j - pos) * 2 + 1;
        }
    }

    int ans = 0;
    for(int j = 1; j <= m; j ++)
        ans = max(ans, solve(palmax[j], n));

    out << ans;

    return 0;
}