Cod sursa(job #639797)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 23 noiembrie 2011 22:59:05
Problema Ferma2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <cstdio>

int v[1001][1001],o[1001][1001],d[1001][1001],sol[1001][1001];

int main()
{
    int res=1000000000,i,j,k,n,sum=0;
    freopen("ferma2.in","r",stdin);
    freopen("ferma2.out","w",stdout);
    scanf("%d%d",&n,&k);
    for (i=1;i<=n;++i)
        for (j=1;j<=i;++j)
        {
            scanf("%d",&v[i][j]);
            sum+=v[i][j];
            o[i][j]=v[i][j]+o[i][j-1];
            d[i][j]=v[i][j]+d[i-1][j-1];
            v[i][j]+=v[i-1][j];
        }
    k=n-k;
    for (i=1;i<=k;++i)
        sol[k][k]+=o[i][i];
    for (i=k+1;i<=n;++i)
    {
        sol[i][k]=sol[i-1][k]+o[i][k]-d[i-1][k];
        for (j=k+1;j<=n;++j)
            sol[i][j]=sol[i][j-1]-v[i][j-k]+v[i-k][j-k]+d[i][j]-d[i-k][j-k];
    }
    for (i=k;i<=n;++i)
        for (j=k;j<=i;++j)
            if (sol[i][j]<res)
                res=sol[i][j];
    printf("%d\n",sum-res);
    return 0;
}