Cod sursa(job #637036)

Utilizator zloteanu.adrianzloteanu adrian nichita zloteanu.adrian Data 20 noiembrie 2011 10:39:59
Problema Ferma2 Scor 30
Compilator cpp Status done
Runda .com 2011 Marime 1.81 kb
#include<fstream>
using namespace std;
int jos[1001][1001];
int dr[1001][1001];
int tr[1001][1001];
int lat[1001][1001];
struct Punct{int x,y;};
struct Triunghi{Punct c1,c2,c3;};
int n,k;
long costm;
void back(Triunghi sursa,int cost,int zt)//zt = cate zile au trecut
{
    if(zt==k)
    {
        if(cost>costm)
         costm=cost;
        return ;
    }
    else
    {
        int costl1=jos[sursa.c2.x][sursa.c2.y]-jos[sursa.c1.x-1][sursa.c1.y];
        int costl2=dr[sursa.c3.x][sursa.c3.y]-dr[sursa.c2.x][sursa.c2.y-1];
        int costl3=lat[sursa.c3.x][sursa.c3.y]-lat[sursa.c1.x-1][sursa.c1.y-1];
        zt++;
        Punct c1,c2,c3;
        Triunghi tr;
        //CAZ 1
        c1.x=sursa.c1.x+1,c1.y=sursa.c1.y+1;
        c2.x=sursa.c2.x,c2.y=sursa.c2.y+1;
        tr.c1=c1;
        tr.c2=c2;
        tr.c3=sursa.c3;
        back(tr,cost+costl1,zt);
        //CAZ 2
        c1=sursa.c1;
        c2=sursa.c2;
        c2.x=c2.x-1;
        c3.x=sursa.c3.x-1;
        c3.y=sursa.c3.y-1;
        tr.c1=c1,tr.c2=c2,tr.c3=c3;
        back(tr,cost+costl2,zt);
        //CAZ 3
        c1=sursa.c1;
        c1.x=c1.x+1;
        c2=sursa.c2;
        c3=sursa.c3;
        c3.y=c3.y-1;
        tr.c1=c1,tr.c2=c2,tr.c3=c3;
        back(tr,cost+costl3,zt);

    }

}
int main()
{
    ifstream q("ferma2.in");
    ofstream w("ferma2.out");
    int val;
    q>>n>>k;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=i;j++)
        {
            q>>val;
            tr[i][j]=val;
            jos[i][j]=jos[i-1][j]+val;
            dr[i][j]=dr[i][j-1]+val;
            lat[i][j]=lat[i-1][j-1]+val;
        }
    Punct c1,c2,c3;
    c1.x=1,c1.y=1,c2.x=n,c2.y=1,c3.x=n,c3.y=n;
    Triunghi tr;
    tr.c1=c1;
    tr.c2=c2;
    tr.c3=c3;
    back(tr,0,0);
    w<<costm;
    return 0;
}