Luogu

分析

看到这个 $n\times m\leq 10^5$，可以考虑根号分治。

• $n\leq m$

首先枚举上下边界 $u,d$。

那么所有拼图可以分为两类：第 $u$ 行到第 $d$ 行均为白色的、第 $u$ 行到第 $v$ 行不均为白色的。

最后的拼法会是所有第一类拼图放在中间，然后左右各接上一个第二类拼图。

于是我们算一下第一类拼图的宽度之和，以及第二类拼图左右最多多少列第 $u$ 行到第 $d$ 行为白色就可以算出答案了。

需要注意的是左右不能接同一块第二类拼图，因此需要记一下次大值。

注意判一下答案在某一块拼图内部的情况。

时间复杂度 $\mathcal{O}(n^2m)=\mathcal{O}(S\sqrt{S})$。

• $n>m$

此时直接枚举上下边界行不通了，但是我们可以考虑换一种方法。

我们枚举每个白格，设它在第 $x$ 行，再找到它上方第一个黑格，设它在第 $y$ 行。那么我们将 $y+1$ 作为上边界，$x$ 作为下边界，然后套用 $n\leq m$ 时的做法即可。

时间复杂度 $\mathcal{O}(nm^2)=\mathcal{O}(S\sqrt{S})$。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,m,s,ans;
int w[N],l[N],r[N];
int a[N],sum[N],up[N];

inline int id(int x,int y) {
    if (x<1||y<1) return 0;
    else return (y-1)*n+x;
}

inline int S(int lx,int ly,int rx,int ry) {
    return sum[id(rx,ry)]-sum[id(lx-1,ry)]-
           sum[id(rx,ly-1)]+sum[id(lx-1,ly-1)];
}
inline void calc(int u,int d) {
    for (re int i=1;i<=s;++i)
        for (re int j=l[i],ss=0;j<=r[i];++j) {
            S(u,j,d,j)?ss=0:++ss;
            ans=max(ans,(d-u+1)*ss);
        }
    int mid=0; pair<int,int> lmx,lmx2,rmx,rmx2;
    for (re int i=1;i<=s;++i) {
        int ls=0,rs=0;
        for (re int j=l[i];j<=r[i];++j) {
            if (!S(u,j,d,j)) ++ls; else break;
        }
        for (re int j=r[i];j>=l[i];--j) {
            if (!S(u,j,d,j)) ++rs; else break;
        }
        if (ls==w[i]) mid+=w[i];
        else {
            if (ls>lmx.first) lmx2=lmx,lmx=make_pair(ls,i);
            else if (ls>lmx2.first) lmx2=make_pair(ls,i);
            if (rs>rmx.first) rmx2=rmx,rmx=make_pair(rs,i);
            else if (rs>rmx2.first) rmx2=make_pair(rs,i);
        }
    }
    if (lmx.second!=rmx.second)
        ans=max(ans,(d-u+1)*(lmx.first+mid+rmx.first));
    else {
        ans=max(ans,(d-u+1)*(lmx.first+mid));
        ans=max(ans,(d-u+1)*(mid+rmx.first));
        ans=max(ans,(d-u+1)*(lmx.first+mid+rmx2.first));
        ans=max(ans,(d-u+1)*(lmx2.first+mid+rmx.first));
    }
}

int main() {
    int T=read();
    while (T--) {
        s=read(),n=read(); m=ans=0;
        for (re int i=1;i<=s;++i) {
            w[i]=read(); l[i]=m+1,m+=w[i],r[i]=m;
            for (re int j=1;j<=n;++j)
                for (re int k=l[i];k<=r[i];++k)
                    scanf("%1d",a+id(j,k));
        }
        for (re int i=1;i<=n;++i)
            for (re int j=1;j<=m;++j)
                sum[id(i,j)]=sum[id(i-1,j)]+sum[id(i,j-1)]
                            -sum[id(i-1,j-1)]+a[id(i,j)];
        for (re int j=1;j<=m;++j) { int p=0;
            for (re int i=1;i<=n;++i) {
                if (a[id(i,j)]) {
                    for (re int k=p+1;k<i;++k) up[id(k,j)]=p;
                    p=i;
                }
                for (re int k=p+1;k<=n;++k) up[id(k,j)]=p;
            }
        }
        if (n<m) {
            for (re int i=1;i<=n;++i)
                for (re int j=i;j<=n;++j)
                    calc(i,j);
        } else {
            for (re int i=1;i<=n;++i)
                for (re int j=1;j<=m;++j)
                    if (!a[id(i,j)]) calc(up[id(i,j)]+1,i);
        }
        printf("%d\n",ans);
    }
    return 0;
}