Cod sursa(job #1112024)

Utilizator thewildnathNathan Wildenberg thewildnath Data 19 februarie 2014 12:51:05
Problema Diviz Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#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;
}