把求相邻两行的值改成，每一种值的出现次数乘积，可以做到$O(nm)$计算权值。 题解(https://www.luogu.com.cn/article/vxv664pd ) ** **

部分分是 $O(nk^2)$和 $O(nk)$。$c_i=0$ 或$c_i=m$ 可以发现每个全$0$ 矩阵都填一样的数，算一下就好了。 $k-2$就算 没发现每行所有数都相等也可以 $f_{i,j}$表示第$i$ 行填了$j$ 个$1$ ，可以建立凸包优化 dp。 $c_i=1$就是正解的 dp，有提示 性吗？ 反正时间复杂度$O（nm+k）$ ，写的烂过不去的话，那就是你太菜了。其实带个 log 跑得飞快

#include<bits/stdc++.h>
using namespace std;
#define int         long long
#define pii         pair<int,int>
#define all(v)      v.begin(),v.end()
#define pb          push_back
#define REP(i,b,e)  for(int i=(b);i<(int)(e);++i)
#define over(x)     {cout<<(x)<<endl;return;}
int n,m,t;
int f[4000005],X,Y,g[1000005],c[1000005];
void Main() {
	cin>>n>>m>>t;
	vector<vector<int>>a(n, vector<int>(m));
	vector<int>cnt(n);
	REP(i,0,n){
		cnt[i]=0;
		vector<int>b;
		REP(j,0,m){
			int x;cin>>x;
			if(x>0)b.pb(x-1);
			else ++cnt[i];
		}
		reverse(all(b));REP(j,0,cnt[i])b.pb(-1);
		reverse(all(b));a[i]=b;
	}
	if(n==1)over(0)
	REP(i,0,t)f[i]=0;
	int ans=0;
	REP(i,0,n-1){
		REP(j,cnt[i],m)++f[a[i][j]];
		REP(j,cnt[i+1],m)ans+=f[a[i+1][j]];
		REP(j,cnt[i],m)--f[a[i][j]];
	}
	REP(j,cnt[1],m)f[a[1][j]]+=cnt[0];
	X=Y=0;int mx=0;
	REP(i,0,t)mx=max(mx,f[i]);
	REP(i,1,n){
        vector<int>T;
        REP(j,cnt[i-1],m)T.pb(a[i-1][j]);
        if(i<n-1)REP(j,cnt[i+1],m)T.pb(a[i+1][j]);
        for(auto j:T)c[j]=0;
        for(auto j:T)++c[j];
        int co=cnt[i]*cnt[i-1];
        X+=co;Y=max(Y+co,mx);mx+=co;
        for(auto j:T)if(c[j]){
            f[j]=max(X+f[j],Y)+c[j]*cnt[i];
            mx=max(mx,f[j]);
            f[j]-=X;c[j]=0;
        }
	}
	mx=0;
	REP(j,0,t)mx=max(mx,max(f[j]+X,Y));
	over(mx+ans)
}
void TC() {
    int tc=1;
    cin>>tc;
	while(tc--){
		Main();
		cout.flush();
	}
}
signed main() {
	return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0;
}
/*
1. CLEAR the arrays (ESPECIALLY multitests)
2. DELETE useless output
 */