Pagini recente » Cod sursa (job #1725306) | Cod sursa (job #2591363) | Cod sursa (job #2701019) | Cod sursa (job #2384217) | Cod sursa (job #1323091)
#include <stdio.h>
#define MAXN 1000
#define MAXM 1000
int rez[MAXN][2 * MAXM + 1];
int v[2 * MAXM + 1], st[2 * MAXM + 1], dr[2 * MAXM + 1];
inline void solve(int lin, int col){
int i, dr = 0, st = 0, ci, j;
for(i = 0; i <= col; i++){
if(i <= dr){
ci = st + dr - i;
if(ci - rez[lin][ci] / 2 >= st)
j = i + rez[lin][ci] / 2 + 1;
else
j = dr + 1;
}
else
j = i + 1;
while(i - (j - i) >= 0 && j <= col && v[j] == v[i - (j - i)])
j++;
j--;
rez[lin][i] = 2 * (j - i) + 1;
if(dr < j){
dr = j;
st = i - (j - i);
}
}
}
inline void parcurg(int *cp, int st, int dr, int pas, int col){
int i, stiv[2 * MAXM + 1], k = 0;
for(i = st; i != dr + pas; i += pas){
while(k > 0 && rez[stiv[k - 1]][col] > rez[i][col]){
cp[stiv[k - 1]] = i;
k--;
}
stiv[k] = i;
k++;
}
while(k > 0){
cp[stiv[k - 1]] = dr + pas;
k--;
}
}
inline int skyline(int n, int col){
parcurg(dr, 0, n, 1, col);
parcurg(st, n, 0, -1, col);
int i, max = 0, x;
for(i = 0; i < n; i++){
x = (dr[i] - st[i] - 1) * (rez[i][col] / 2);
if(x > max)
max = x;
}
return max;
}
int main(){
FILE *in = fopen("dreptpal.in", "r");
int n, m, i, j;
fscanf(in, "%d%d", &n, &m);
for(i = 0; i < n; i++){
for(j = 0; j < m; j++){
fscanf(in, "%d", &v[2 * j + 1]);
}
solve(i, 2 * m);
}
int max = 0, r;
for(i = 0; i <= 2 * m; i++){
r = skyline(n - 1, i);
if(r > max)
max = r;
}
FILE *out = fopen("dreptpal.out", "w");
fprintf(out, "%d", max);
fclose(out);
return 0;
}