Cod sursa(job #635857)

Utilizator savimSerban Andrei Stan savim Data 19 noiembrie 2011 15:17:57
Problema DreptPal Scor 50
Compilator cpp Status done
Runda .com 2011 Marime 1.78 kb
#include <fstream>
#include <cstring>
#include <algorithm>

using namespace std;

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

#define MAX_N 1010

int n, m, last;

int A[MAX_N][MAX_N], d[MAX_N][MAX_N];

inline int get_min(int x, int y) {
    return x < y ? x : y;
}

inline int get_max(int x, int y) {
    return x > y ? x : y;
}

void get_pal() {
    int X[MAX_N], Y[MAX_N];

	for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            X[j] = A[i][j];
            Y[j] = 0;
        }

        for (int j = 1; j <= m; j++) {
    		if (j == 1) {
		    	Y[j] = 1;
            	last = 1;
    		}
	    	else 
    			Y[j] = get_max(get_min(Y[last - (j - last)] - 1, last + Y[last] - j), 1);

    		int left = j - Y[j], right = j + Y[j];
    		while (0 < left && right <= m && X[left] == X[right]) {
            	Y[j]++;
    			left--;
    			right++;
    		}

    		if (j + Y[j] > last + Y[last])
    			last = i;
        }

        for (int j = 1; j <= m; j++)
            d[i][j] = Y[j];
	}
}

int get_sol() {
    int V[MAX_N];
    memset(V, 0, sizeof(V));

    int ans = 0;

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

        d[n + 1][j] = 0;
        for (int i = 1; i <= n + 1; i++) {
            V[++k] = i;
        
            while (d[V[k]][j] <= d[V[k - 1]][j] && k > 1) {
                int st = (k > 2) ? V[k - 2] + 1 : 1;
                int dr = V[k] - 1;

                ans = get_max(ans, (dr - st + 1) * d[V[k - 1]][j] * 2 - (dr - st + 1));

                V[k - 1] = V[k];
                V[k--] = 0;
            }

        }
    }

    return ans;
}

int main() {

    f >> n >> m;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) 
            f >> A[i][j];
        A[i][m + 1] = -1;
    }

    get_pal();

    g << get_sol();

	return 0;
}