Cod sursa(job #636824)

Utilizator savimSerban Andrei Stan savim Data 20 noiembrie 2011 00:03:24
Problema DreptPal Scor 0
Compilator cpp Status done
Runda .com 2011 Marime 1.57 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() {
	for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
    		if (j == 1) {
		    	d[i][j] = 1;
            	last = 1;
    		}
	    	else 
    			d[i][j] = get_max(get_min(d[i][last - (j - last)] - 1, last + d[i][last] - j), 1);

    		while (0 < j - d[i][j] && j + d[i][j] <= m && A[i][j - d[i][j]] == A[i][j + d[i][j]])
            	d[i][j]++;

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

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