Cod sursa(job #1798216)

Utilizator demetriad-dagpagDavid Demetriad demetriad-dagpag Data 4 noiembrie 2016 22:36:14
Problema Ferma2 Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <stdio.h>
#include <stdlib.h>
int a[1001][1001],sumv[1001][1001],sumo[1001][1001],rez[1001][1001],sumd[1001][1001];
int main()
{
    int i,j,n,k,min,s,x;
    freopen("ferma2.in","r",stdin);
    freopen("ferma2.out","w",stdout);
    scanf("%d%d",&n,&k);
    s=0;
    for(i=1; i<=n; i++)
        for(j=1; j<=i; j++){
            scanf("%d",&a[i][j]);
            s+=a[i][j];
        }
    for(i=1; i<=n; i++)
        for(j=1; j<=i; j++)
            sumv[i][j]=sumv[i-1][j]+a[i][j];
    for(i=1; i<=n; i++)
        for(j=1; j<=i; j++)
            sumo[i][j]=sumo[i][j-1]+a[i][j];
    for(i=1; i<=n; i++)
    {
        x=i;
        j=1;
        while(x<=n)
        {
            sumd[x][j]=sumd[x-1][j-1]+a[x][j];
            x++;
            j++;
        }
    }
    for(i=1; i<=n-k; i++)
        for(j=1; j<=i; j++)
            rez[n-k][1]+=a[i][j];
    min=rez[n-k][1];
    for(i=n-k+1,j=2; i<=n; i++,j++){
        rez[i][j]=rez[i-1][j-1]-(sumv[i-1][j-1]-sumv[i-1-(n-k)][j-1])+(sumo[i][j+(n-k)-1]-sumo[i][j-1]);
        if(rez[i][j]<min)
            min=rez[i][j];
    }
    for(i=n-k+1; i<=n; i++)
        for(j=1; j<i-n+k+1; j++){
            rez[i][j]=rez[i-1][j]-(sumd[i-1][j+(n-k)-1]-sumd[i-1-(n-k)][j-1])+(sumo[i][j+(n-k)-1]-sumo[i][j-1]);
            if(rez[i][j]<min)
                min=rez[i][j];
        }
    printf("%d\n",s-min);

    return 0;
}