19 nowcoder 第二场 经典dp延伸，单调队列变量维护 H Second Large Rectangle

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1011;
int a[maxn][maxn],d[maxn][maxn];
int max_1,max_2;
char s[maxn][maxn];
int t[maxn],q[maxn];
void upda(int x){
	if(x>max_1){
		max_2 = max_1;
		max_1 = x;
	}else if(x>max_2){
		max_2 = x;
	}
}
int main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	getchar();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%c",&s[i][j]);
			if(s[i][j]=='1') d[i][j] = d[i-1][j]+1; 
			else d[i][j]=0;
		}
		getchar();
	}
	int r = 0;
	for(int i=1;i<=n;i++){
		r  = 0;
		for(int j=1;j<=m+1;j++){
            int l = j;
			while(r && d[i][j] < t[r] ){
				int x = t[r], y = j - q[r];
				upda(x*y);	upda((x-1)*y);	upda(x*(y-1));
				l = q[r];
				r--;
			}
			if(d[i][j]){
				q[++r] = l;
				t[r] = d[i][j]; 	
			}
		}
	}
	printf("%d\n",max_2);
	return 0;
}
/*
4 5
11011
11111
01100
01100

*/