Cod sursa(job #2458316)

Utilizator Iulia25Hosu Iulia Iulia25 Data 20 septembrie 2019 10:44:33
Problema DreptPal Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <fstream>
#include <deque>

using namespace std;

ifstream fin ("dreptpal.in");
ofstream fout ("dreptpal.out");

int n, m, k, Max, val;
int v[1005];
int a[1005][1005];

deque <pair <int, int>> s;

int main()  {
	fin >> n >> m;
	for (int i = 1; i <= n; ++i)  {
		for (int j = 1; j <= m; ++j)  {
			fin >> v[j];
		}
		int mij = 0, r = 0;
		for (int j = 1; j <= m; ++j)  {
			if (j < r)  {
				if (a[i][mij - (j - mij)] + j < r)
					a[i][j] = a[i][mij - (j - mij)];
				else  {
					int x = r - j;
					while (v[j + x] == v[j - x] && j + x <= m && j - x >= 1)
						++x;
					--x;
					mij = j;
					r = j + x;
					a[i][j] = x;
				}
			} else  {
				int x = 1;
				while (v[j + x] == v[j - x] && j + x <= m && j - x >= 1)
					++x;
				--x;
				mij = j;
				r = j + x;
				a[i][j] = x;
			}
			a[i][j] = 2 * a[i][j] + 1;
		}
	}
	for (int j = 1; j <= m; ++j)  {
    for (int i = 1; i <= n; ++i)  {
      k = i;
      while (!s.empty() && s.back().second > a[i][j])  {
        k = s.back().first;
        val = s.back().second;
        if (val * (i - k) > Max)
          Max = val * (i - k);
        s.pop_back();
      }
      s.push_back({k, a[i][j]});
    }
    while (!s.empty())  {
      k = s.back().first;
      val = s.back().second;
      if (val * (n - k + 1) > Max)
        Max = val * (n - k + 1);
      s.pop_back();
    }
  }
  fout << Max;
	return 0;
}