Cod sursa(job #2010593)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 13 august 2017 18:19:33
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <bits/stdc++.h>

FILE *fi, *fout;

const int MAXBUF = (1 << 17);

char buf[MAXBUF];
int pbuf = MAXBUF;

inline char nextch() {
   if(pbuf == MAXBUF) {
      fread(buf, 1, MAXBUF, fi);
      pbuf = 0;
   }
   return buf[pbuf++];
}

inline int getnr() {
   char ch = nextch();
   while(!isdigit(ch))
     ch = nextch();
   int nr = 0;
   while(isdigit(ch)) {
      nr = nr * 10 + ch - '0';
      ch = nextch();
   }
   return nr;
}

const int MAXN = (int) 1e3;

int str[2 * MAXN + 10];
int man[2 * MAXN + 1];

int len[MAXN + 1][MAXN + 1];

struct Data {
    int l;
    int high;
};

std::stack <Data> stk;

int main() {
    int i, j, n, m;
    fi = fopen("dreptpal.in" ,"r");
    fout = fopen("dreptpal.out" ,"w");
    n = getnr();
    m = getnr();
    for(i = 1; i <= n; i++) {
        int sz = 1;
        str[1] = -1;
        for(j = 1; j <= m; j++) {
            str[++sz] = getnr();
            str[++sz] = -1;
        }
        int p = 0;
        for(j = 1; j <= sz; j++) {
            if(p + man[p] - 1 < j)
                man[j] = 1;
            else
                man[j] = std::min(man[2 * p - j], p + man[p] - j);
            while(j - man[j] > 0 && j + man[j] <= sz && str[j - man[j]] == str[j + man[j]])
                man[j]++;
            if(j + man[j] > p + man[p])
                p = j;
        }
        for(j = 2; j <= sz; j += 2)
            len[i][j / 2] = man[j] - 1;
    }
    int ans = 0;
    for(j = 1; j <= m; j++) {
        int l;
        for(i = 1; i <= n; i++) {
             l = 0;
             while(!stk.empty() && stk.top().high >= len[i][j]) {
                  l += stk.top().l;
                  ans = std::max(ans, l * stk.top().high);
                  stk.pop();
             }
             stk.push({l + 1, len[i][j]});
        }
        l = 0;
        while(!stk.empty()) {
             l += stk.top().l;
             ans = std::max(ans, l * stk.top().high);
             stk.pop();
        }
    }
    fprintf(fout,"%d" ,ans);
    fclose(fi);
    fclose(fout);
    return 0;
}