Cod sursa(job #2466954)

Utilizator theo2003Theodor Negrescu theo2003 Data 3 octombrie 2019 12:46:38
Problema DreptPal Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("dreptpal.in");
ofstream cout("dreptpal.out");
int pal[1000][1000];
int main() {
    int n, m;
    cin>>n>>m;
    for(int ro = 0; ro<n; ro++) {
        int tmp[1000];
        for(int x = 0; x<m; x++) {
            cin>>tmp[x];
        }
        for(int x = 0, l = 0, r = -1; x<m; x++) {
            int ex = 1;
            if(x <= r) {
                ex = min(r - x + 1, pal[ro][r + l - x]);
            }
            while((tmp[x - ex] == tmp[x + ex]) && ((x + ex) < m) && ((x - ex) >= 0)) {
                ex++;
            }
            pal[ro][x] = ex--;
            if((x + ex) > r) {
                l = x - ex;
                r = x + ex;
            }
        }
    }
    for(int ro = 0; ro<n; ro++) {
        for(int x = 0; x<m; x++) {
            pal[ro][x] = (pal[ro][x] - 1)*2 + 1;
        }
    }
    long long int actual_max = -1;
    for(int align = 0; align<m; align++) {
        vector<pair<int, int> > p;
        p.push_back({0,0});
        long long int maxp = 0;
        for(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(int x = 0;x<p.size();x++)
                p[x].second++;
            long long int maxpp = -1;
            for(int i = p.size() - 1, ps = 0; i>=0; i--) {
                if((p[i].second + ps)*p[i].first > maxpp) {
                    maxpp = (p[i].second + ps)*p[i].first;
                }
                //ps += p[i].second;
            }
            maxp = max(maxp, maxpp);

        }
        actual_max = max(actual_max, maxp);
    }
    cout<<actual_max;
    return 0;
}