比赛 随便比赛 评测结果 TTTTAATTTR
题目名称 Partition 最终得分 20
用户昵称 健康铀 运行时间 22.062 s
代码语言 C++ 内存使用 140.40 MiB
提交时间 2024-08-27 20:43:25
显示代码纯文本
#include<bits/stdc++.h>
#define ll long long
#define maxn 2005
using namespace std;
ll n,m,mp[maxn][maxn],pre[maxn][maxn],sum,ans,dmp[maxn][maxn];
bool det(int x, int y) {
	int now,c=dmp[x][y];
	if(x>1) {
		now=dmp[x-1][y];
		if(c==1&&now!=1) return false;
		if(c==2&&(now==3||now==4)) return false;
		if(c==3&&(now==2||now==4)) return false;
	}
	if(y>1) {
		now=dmp[x][y-1];
		if(c==1&&(now==2||now==4)) return false;
		if(c==4&&(now==1||now==2)) return false;
		if(c==3&&now!=3) return false;
	}
	return true;
}
void dfs(int x, int y) {
	for(int i=1; i<=4;i++) {
		dmp[x][y]=i;
		if(!det(x,y)) continue;
		sum+=mp[x][y]*i;
		if(x==n&&y==m) {
			ans=max(ans,sum);
		} else if(y==m) {
			dfs(x+1,1);
		} else dfs(x,y+1);
		sum-=mp[x][y]*i;
	}
}
int main() {
    freopen("partition.in","r",stdin);
    freopen("partition.out","w",stdout);
	cin>>n>>m;
	bool flag=true;
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			scanf("%ld",&mp[i][j]);
			if(mp[i][j]<0)flag=false;
		}
	}
	if(flag) {
		ll sum = 0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)sum+=mp[i][j];
		sum*=4;
		cout<<sum<<endl;
		return 0;
	}
	ans=LLONG_MIN;
	sum=0;
	dfs(1,1);
	cout<<ans<<endl;
	return 0;
}