AcWing 152. 城市游戏
原题链接
中等
作者:
开始独自升级
,
2023-12-01 11:10:36
,
所有人可见
,
阅读 51
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int s[N][N];
int n,m;
int solve(int a[])
{
int stk[N];
int tt;
int w[N];
a[0]=a[m+1]=0;
tt=0;
stk[tt]=0;
for(int i=1;i<=m;i++)
{
while(tt!=0&&a[stk[tt]]>=a[i])
tt--;
w[i]=i-stk[tt];
stk[++tt]=i;
}
tt=0;
stk[tt]=m+1;
for(int i=m;i>=1;i--)
{
while(tt!=0&&a[stk[tt]]>=a[i])
tt--;
w[i]+=stk[tt]-i;
stk[++tt]=i;
}
int sum=0;
for(int i=1;i<=m;i++)
sum=max(sum,(w[i]-1)*a[i]);
return sum;
}
int main()
{
cin>>n>>m;
char c;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>c;
if(c=='F')
s[i][j]=s[i-1][j]+1;
}
int res=0;
for(int i=1;i<=n;i++)
res=max(res,solve(s[i]));
cout<<res*3<<endl;
return 0;
}