Pagini recente » Cod sursa (job #1339852) | Cod sursa (job #31883) | Cod sursa (job #42415) | Cod sursa (job #2938426) | Cod sursa (job #2663489)
#include<bits/stdc++.h>
#define fore(start,i,end) for(int i = start; i <= end; i++)
#define dbg(x) #x << "=" << x << " "
#define dbg2(x,y) "{" << x << "," << y << "} "
#define dbg3(x,y,k) "{" << x << "," << y << "," << k << "} "
#define dbg4(x,y,k,j) "{" << x << "," << y << "," << k << " , " << j << "} "
#define ll long long
#define f1 first
#define f2 second
#define inf 1000000005
#define debug_st(st) if (true) {cout << #st << " : "; stack<int> s123; while (!s123.empty()) cout << s123.top() << " ", s123.pop(); cout << "\n";}
#define debug_a(a,n) cout << #a << " : "; for(int i = 1; i <= n; i++) cout << a[i] << " "; cout << "\n";
#define debug_m(a,n,m) cout << #a << " :\n"; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++) cout << a[i][j] << " "; cout << "\n"; }cout << "\n";
#define debug_v(v) cout << #v << " : "; for(auto k : v) cout << k << " "; cout << "\n";
#define debug_s(s) cout << #s << " : "; for (auto k : s) cout << k < " "; cout << "\n";
#define debug_s2(s) cout << #s << " : "; for(auto k : s) cout << dbg2((*k).first,(*k).second); cout << "\n";
#define nmax 1005
using namespace std;
ifstream in("dreptpal.in");
ofstream out("dreptpal.out");
ll a[nmax][nmax],n,m,p[nmax][nmax],v[nmax],sol;
ll Extend(ll i, ll bonus, ll v[nmax])
{
//cout << "EXTEND i = " << i << "\n";
ll p = i + bonus + 1,poz = i + bonus;
while (p <= m && v[p] == v[i - (p - i)])
{
poz = p++;
}
//cout << "poz = " << poz << "\n";
return poz;
}
void get_p(ll v[nmax],ll p[nmax])
{ll i;
ll mij = 0,dr = 0;
for (i = 1; i <= m; i++)
{
///daca dr este in spatele nostru, ne exstindem cat putem, clar
///daca dr este dupa i
/// dr i mij i dr p[i] = p[mij - (i - mij)] dupaia daca e mai mare de dr
///il putem extinde
if (dr < i)
{
int poz = Extend(i , 0 , v); /// cate de mult se poate extinde.
p[i] = (poz - i + 1);
mij = i;
dr = poz;
}
else
{
p[i] = p[mij - (i - mij)];
if (i + p[i] < dr)
{
continue;
}
p[i] = min(p[i] , dr - i + 1);
int poz = Extend(i , p[i] - 1 , v);
dr = poz;
p[i] = poz - i + 1;
mij = i;
}
}
// debug_a(v , m);
// debug_a(p ,m);cout << "\n\n";
}
stack<ll> q;
ll st[nmax],dr[nmax];
void solve(ll v[nmax],ll col)
{ll i;
while (!q.empty())q.pop();
for (i = 1; i <= n; i++)
{
while (!q.empty() && v[i] < v[q.top()])
{
q.pop();
}
if (q.empty())
st[i] = i;
else
st[i] = i - q.top();
q.push(i);
}
while (!q.empty())q.pop();
for (i = n; i >= 1; i--)
{
while (!q.empty() && v[i] < v[q.top()])
{
q.pop();
}
if (q.empty())
{
dr[i] = n - i +1;
}
else
dr[i] = q.top() - i;
}
for (i = 1; i <= n; i++)
{
sol = max(sol , p[i][col] * (st[i] + dr[i] - 1));
}
//debug_a(v , n);
// for (i = 1; i <= n; i++)
// {
// cout << dbg(i) << dbg(st[i])<< dbg(dr[i]) << "\n";
// }cout << "\n";
}
int main()
{ll i,j;
in >> n >> m;
for (i = 1; i <= n; i++)
{
for (j = 1; j <= m; j++)
in >> a[i][j];
}
for (i = 1; i <= n; i++)
{
get_p(a[i],p[i]);
}
for (j = 1; j <= m; j++)
{
for (i = 1; i <= n; i++)
{
v[i] = a[i][j];
}
solve(v,j);
}out << sol << "\n";
}