Cod sursa(job #2712855)

Utilizator LuciBBadea Lucian LuciB Data 26 februarie 2021 17:41:55
Problema Fractii Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.16 kb
#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;
}