比赛 |
随便比赛 |
评测结果 |
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;
}