蒟蒻64分求助
  • 板块P4147 玉蟾宫
  • 楼主fchwpo
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/8/13 22:48
  • 上次更新2023/11/3 03:59:53
查看原帖
蒟蒻64分求助
831879
fchwpo楼主2023/8/13 22:48
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1055;
int up[maxn][maxn];
int ans;
int n,m;
char c[maxn][maxn];
struct node{
	int val,pos;
};
bool flag;
signed main(){
//	ios::sync_with_stdio(false);
//	cin.tie(0);
//	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>c[i][j];
			if(c[i][j]=='F'){
				flag=1;
			}
		}
	}
	if(!flag){
		cout<<0;
		return 0;
	}
	for(int i=1;i<=m;i++){
		up[n+1][i]=n+1;
	}
	for(int i=n;i;i--){
		for(int j=1;j<=m;j++){
			if(c[i][j]=='R'){
				up[i][j]=i;
			}
			else{
				up[i][j]=up[i+1][j];
			}
		}
	}

	for(int i=1;i<=n;i++){
		stack<node>ncw;
		ncw.push(node{up[i][1],1});
		for(int j=2;j<=m;j++){
			if(ncw.top().val<up[i][j]){
				ncw.push(node{up[i][j],j});
			}
			else if(ncw.top().val>up[i][j]){
				int cntt=0;
				while((!ncw.empty())&&ncw.top().val>up[i][j]){
					cntt++;
					ans=max((j-ncw.top().pos)*(ncw.top().val-i),ans);
//					cout<<ans<<" "<<i<<" "<<j<<" "<<(ncw.top().pos)<<" "<<(ncw.top().val)<<'\n';
					ncw.pop();
				}
				ncw.push(node{up[i][j],j});
			}
		}
	
		while(!ncw.empty()){
			ans=max((m-ncw.top().pos+1)*(ncw.top().val-i),ans);
//				cout<<ans<<" "<<i<<" "<<(ncw.top().pos)<<" "<<(ncw.top().val)<<'\n';
			ncw.pop();
		}
	}
	cout<<ans*3;
	return 0;
}

2023/8/13 22:48
加载中...