Cod sursa(job #638627)

Utilizator gramatovici_paulGramatovici Paul gramatovici_paul Data 21 noiembrie 2011 09:57:04
Problema Ferma2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream in("ferma2.in");
ofstream out("ferma2.out");


int n,k,a[1010][1010],sum,lin[1010][1010],col[1010][1010],diag[1010][1010],s[1010][1010],minim;


int main()
{
    int i,j;
    in>>n>>k;
    for(i=1;i<=n;++i)
        for(j=1;j<=i;++j)
        {
            in>>a[i][j];
            sum+=a[i][j];
        }
    k=n-k;
    for(i=1;i<=n;++i)
    {
        for(j=1;j<=i;++j)
        {
            lin[i][j]=lin[i][j-1]+a[i][j];
            col[i][j]=col[i-1][j]+a[i][j];
            diag[i][j]=diag[i-1][j-1]+a[i][j];
        }
    }
    for(i=1;i<=k;++i)
    {
        for(j=1;j<=i;++j)
            s[1][1]+=a[i][j];
    }
    minim=s[1][1];
    for(i=2;i<=n-k+1;++i)
    {
        s[i][1]=s[i-1][1]-diag[i-2+k][k]+lin[i-1+k][k];
        if(minim>s[i][1])
            minim=s[i][1];
        for(j=2;j<=i;++j)
        {
            s[i][j]=s[i][j-1]-col[i+k-1][j-1]+col[i-1][j-1]+diag[i+k-1][j+k-1]-diag[i-1][j-1];
            if(s[i][j]<minim)
                minim=s[i][j];
        }
    }
    out<<sum-minim;
    return 0;
}