Pagini recente » Cod sursa (job #1233027) | Cod sursa (job #2506745) | Cod sursa (job #2983637) | Cod sursa (job #2253441) | Cod sursa (job #2712855)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("poteci.in");
ofstream fout ("poteci.out");
int a[1001][1001];
int dp[4][1001][1001];
int l, c;
const int MAX=100000;
int startPoints[4][4]={
{1, l, 1, c},
{l, 1, c, 1},
{1, l, c, 1},
{l, 1, 1, c}
};
int sign[4][2]{
{ 1, 1},
{-1, -1},
{ 1, -1},
{-1, 1}
};
int dir[4][4]={
{-1, 0, 0, -1},
{ 1, 0, 0, 1},
{-1, 0, 0, 1},
{ 1, 0, 0, -1}
};
int maxim (int a, int b){
return a>b?a:b;
}
int main(){
int maxx=0, lans=-1, cans=-1;
fin>>l>>c;
for(int i=1; i<=l; i++)
for(int j=1; j<=c; j++)
fin>>a[i][j];
startPoints[0][1]=startPoints[1][0]=startPoints[2][1]=startPoints[3][0]=l;
startPoints[0][3]=startPoints[1][2]=startPoints[2][2]=startPoints[3][3]=c;
/*for(int x=0; x<4; x++){
for(int y=0; y<4; y++)
cout<<startPoints[x][y]<<' ';
cout<<endl;
}*/
for(int x=0; x<4; x++){
if(x==0){
a[1][c]-=MAX;
a[l][1]-=MAX;
}else if(x==2){
a[1][c]+=MAX;
a[l][1]+=MAX;
}
for(int i=startPoints[x][0]; i*sign[x][0]<=startPoints[x][1]*sign[x][0]; i+=sign[x][0])
for(int j=startPoints[x][2]; j*sign[x][1]<=startPoints[x][3]*sign[x][1]; j+=sign[x][1])
dp[x][i][j]=a[i][j]+maxim(dp[x][ i+dir[x][0] ][ j+dir[x][1] ], dp[x][ i+dir[x][2] ][ j+dir[x][3] ]);
if(x==2){
a[1][1]-=MAX;
a[l][c]-=MAX;
}else if(x==4){
a[1][1]+=MAX;
a[l][c]+=MAX;
}
}
for(int i=1; i<=l; i++){
for(int j=1; j<=c; j++){
if(!(i==1 && j==1) && !(i==l && j==c) && !(i==l && j==1) && !(i==1 && j==c)){
int val=0;
for(int x=0; x<4; x++)
val+=dp[x][i][j];
val-=2*a[i][j];
if(val>maxx){
maxx=val;
lans=i;
cans=j;
}
}
}
}
fout<<maxx<<endl<<lans<<' '<<cans;
fin.close();
fout.close();
return 0;
}