Cod sursa(job #2466959)

Utilizator theo2003Theodor Negrescu theo2003 Data 3 octombrie 2019 13:08:49
Problema DreptPal Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("dreptpal.in");
ofstream cout("dreptpal.out");
long long int pal[1001][1001];
int main() {
    long long int n, m;
    cin>>n>>m;
    for(long long int ro = 0; ro<n; ro++) {
        long long int tmp[1001];
        for(long long int x = 0; x<m; x++) {
            cin>>tmp[x];
        }
        for(long long int x = 0, l = 0, r = -1; x<m; x++) {
            long long int ex = 1;
            if(x <= r) {
                ex = min(r - x + 1, pal[ro][r + l - x]);
            }
            while(((x + ex) < m) && ((x - ex) >= 0) && (tmp[x - ex] == tmp[x + ex])) {
                ex++;
            }
            pal[ro][x] = ex--;
            if((x + ex) > r) {
                l = x - ex;
                r = x + ex;
            }
        }
    }
    for(long long int ro = 0; ro<n; ro++) {
        for(long long int x = 0; x<m; x++) {
            pal[ro][x] = (pal[ro][x] - 1)*2 + 1;
        }
    }
    long long int actual_max = 0;
    for(long long int align = 0; align<m; align++) {
        vector<pair<int, int> > p;
        p.push_back({0,0});
        long long int maxp = 0;
        for(long long int x = 0; x<n; x++) {
            auto f = upper_bound(p.begin(), p.end(), pair<int, int>(pal[x][align], 0), [](pair<int, int> a, pair<int, int> b) {
                return a.first < b.first;
            });
            p.erase(f, p.end());
            if((p.end()-1)->first != pal[x][align]){
                p.push_back(pair<int, int>(pal[x][align], 0));
            }
            for(size_t x = 0;x<p.size();x++)
                p[x].second++;
            long long int maxpp = 0;
            for(long long int i = p.size() - 1; i>=0; i--) {
                if((p[i].second*p[i].first) > maxpp) {
                    maxpp = p[i].second*p[i].first;
                }
            }
            maxp = max(maxp, maxpp);
        }
        actual_max = max(actual_max, maxp);
    }
    cout<<actual_max;
    return 0;
}