Cod sursa(job #752251)

Utilizator anca1243Popescu Anca anca1243 Data 28 mai 2012 10:46:05
Problema Indep Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("joc.in");
ofstream out("joc.out");
const int N=1005,M=1005;
int n,m,a[N][M],d[N][M],dmax=-100000,di,dj;
int maxim(int a, int b)
{
    if(a>b) return a;
    return b;
}
void rez()
{
    d[1][1] = a[1][1];
    di = dj = 1;
    for(int i=2;i<=n;i++)
    {
        d[i][1]=maxim(d[i-1][1],a[i][1]-d[i-1][1]);
        if(d[i][1]>dmax)
        {
            dmax=d[i][1];
            di=i; dj=1;
        }
    }
    for(int j=2;j<=m;j++)
    {
        d[1][j]=maxim(d[1][j-1],a[1][j]-d[1][j-1]);
        if(d[1][j]>dmax)
        {
            dmax=d[1][j];
            di=1; dj=j;
        }
    }
    for(int i=2;i<=n;i++)
        for(int j=2;j<=m;j++)
        {
            if(a[i][j]-max(d[i-1][j],d[i][j-1]) < max(d[i-1][j],d[i][j-1]))
            {
                d[i][j]=max(d[i-1][j],d[i][j-1]);
            }
            else
            {
                d[i][j]=a[i][j]-max(d[i-1][j],d[i][j-1]);
            }
            if(d[i][j]>dmax)
            {
                dmax=d[i][j];
                di=i; dj=j;
            }
        }
}
int main()
{
    int i,j;
    in>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            in>>a[i][j];
    rez();

    out<<dmax<<' '<<di<<' '<<dj;
    return 0;
}