Pagini recente » Cod sursa (job #1519242) | Cod sursa (job #1530514) | Cod sursa (job #1392976) | Cod sursa (job #2024227) | Cod sursa (job #1112025)
#include<stdio.h>
#include<algorithm>
using namespace std;
#define NMAX 1002
#define INF 2000000000
int dp[NMAX][NMAX][2];
int dx[]={0,0,1,1},dy[]={0,1,1,0};
int main()
{
freopen("joc.in","r",stdin);
freopen("joc.out","w",stdout);
int n,m,i,j,x,k,sol=-INF,sx,sy,maxi,mini;
scanf("%d%d",&n,&m);
for(i=0;i<=n;++i)
for(j=0;j<=m;++j)
{
dp[i][j][0]=-INF;
dp[i][j][1]=INF;
}
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)
{
scanf("%d",&x);
if(i==1&&j==1)
{
dp[i][j][0]=x;
dp[i][j][1]=-x;
continue;
}
mini=INF;
maxi=-INF;
for(k=1;k<=3;++k)
{
if(i<=dx[k]||j<=dy[k])continue;
dp[i][j][0]=max(dp[i][j][0],dp[i-dx[k]][j-dy[k]][0]);
dp[i][j][1]=min(dp[i][j][1],dp[i-dx[k]][j-dy[k]][1]);
mini=min(mini,dp[i-dx[k]][j-dy[k]][1]);
maxi=max(maxi,dp[i-dx[k]][j-dy[k]][0]);
}
dp[i][j][0]=max(dp[i][j][0],mini+x);
dp[i][j][1]=min(dp[i][j][1],maxi-x);
}
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)
if(dp[i][j][0]>sol)
{
sol=dp[i][j][0];
sx=i;
sy=j;
//printf("%d %d %d\n",sol,sx,sy);
}
printf("%d %d %d\n",sol,sx,sy);
return 0;
}