COCI NEO —— 单调栈求最大全1子矩阵

应该能进

题意：

现在有一个n*m的矩阵，定义一个矩阵(r>=2,c>=2)是cool的当

a[i][j]+a[i-1][j-1]<=a[i][j-1]+a[i-1][j]

定义一个矩阵是非常cool的，当所有它的子矩阵(r>=2,c>=2)是cool的。问你这个矩阵中非常cool 的矩阵最多包含的点的数量是多少。

题解：

这个题意我搞了好久…coci每一场比赛我都很难受因为我搞不懂他的题意。
然后的话，我们可以发现一个规律：

对于这样两个矩阵，如果他们都是cool的，也就是说
$a+e<=b+d\&\&b+f<=c+e$a+e<=b+d&&b+f<=c+e
那么两个式子合并：
$a+e+b+f\le b+d+c+e$a+e+b+f≤b+d+c+e
$=>a+f\le c+d$=>a+f≤c+d
那么就是说如果两个相邻的同高或者同宽的矩阵都是cool的话，那么整个就是cool的。于是我们做出所有2*2的矩阵的情况，如果是cool的，就将右下角的值置为1，然后就找最大01子矩阵就ok啦。
注意要用快读，但是我的快读在这里不能用？用了别人的快读

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
using namespace std;
namespace Fast_IO { //orz laofu
	const int MAXL((1 << 18) + 1); int iof, iotp;
	char ioif[MAXL], * ioiS, * ioiT, ioof[MAXL], * iooS = ioof, * iooT = ioof + MAXL - 1, ioc, iost[55];
	char Getchar() {
		if (ioiS == ioiT) {
			ioiS = ioif; ioiT = ioiS + fread(ioif, 1, MAXL, stdin); return (ioiS == ioiT ? EOF : *ioiS++);
		}
		else return (*ioiS++);
	}
	void Write() { fwrite(ioof, 1, iooS - ioof, stdout); iooS = ioof; }
	void Putchar(char x) { *iooS++ = x; if (iooS == iooT)Write(); }
	inline int read() {
		int x = 0; for (iof = 1, ioc = Getchar(); ioc<'0' || ioc>'9';)iof = ioc == '-' ? -1 : 1, ioc = Getchar();
		for (x = 0; ioc <= '9' && ioc >= '0'; ioc = Getchar())x = (x << 3) + (x << 1) + (ioc ^ 48); return x * iof;
	}
	inline long long read_ll() {
		long long x = 0; for (iof = 1, ioc = Getchar(); ioc<'0' || ioc>'9';)iof = ioc == '-' ? -1 : 1, ioc = Getchar();
		for (x = 0; ioc <= '9' && ioc >= '0'; ioc = Getchar())x = (x << 3) + (x << 1) + (ioc ^ 48); return x * iof;
	}
	template <class Int>void Print(Int x, char ch = '\0') {
		if (!x)Putchar('0'); if (x < 0)Putchar('-'), x = -x; while (x)iost[++iotp] = x % 10 + '0', x /= 10;
		while (iotp)Putchar(iost[iotp--]); if (ch)Putchar(ch);
	}
	void Getstr(char* s, int& l) {
		for (ioc = Getchar(); ioc <'a' || ioc>'z';)ioc = Getchar();
		for (l = 0; ioc <= 'z' && ioc >= 'a'; ioc = Getchar())s[l++] = ioc; s[l] = 0;
	}
	void Putstr(const char* s) { for (int i = 0, n = strlen(s); i < n; ++i)Putchar(s[i]); }
} // namespace Fast_IO
using namespace Fast_IO;
int sum[N][N],d[N][N];
struct node{
    int id,x;
};
stack<node>st;
int a[N][N];
int main()
{
    int n,m;
    n=read(),m=read();
    //scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j]=read();
            //scanf("%d",&a[i][j]);
            if(i==1||j==1)d[i][j]=0;
            else if(a[i][j]+a[i-1][j-1]<=a[i][j-1]+a[i-1][j])d[i][j]=1;
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        while(!st.empty())st.pop();
        for(int j=1;j<=m+1;j++){
            if(d[i][j])sum[i][j]=sum[i-1][j]+1;
            int id=-1;
            while(!st.empty()&&st.top().x>sum[i][j]){
                ans=max(ans,st.top().x*(j-st.top().id)+st.top().x+j-st.top().id+1);
                id=st.top().id;
                st.pop();
            }
            if(st.empty())
                ans=max(ans,sum[i][j]*j+sum[i][j]+j+1);
            if(id==-1)id=j;
            st.push({id,sum[i][j]});
        }
    }
    printf("%d\n",ans?ans:-1);
}
/*
3 3
1 111 10
5 111 116
1 111 2

*/