Cod sursa(job #2306449)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 22 decembrie 2018 13:11:40
Problema DreptPal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.01 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;
    stk[++sz] = start - add;

    for(int i = start; 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(vector<int> &v, int n) {
    v[0] = -1;
    v[n + 1] = -1;

    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]);
       // cout << i << " " << distoleft[i] << " " << distoright[i] << endl;
    }

    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;
            }

            for(int k = p[j]; k >= 1; k --) {
                palmax[j + k - 1][i] = max(palmax[j + k - 1][i], k * 2 - 1);
            }
        }
    }

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

    out << ans;

    return 0;
}