Cod sursa(job #637274)

Utilizator Fetita_JucausaFetita Buclucasa Fetita_Jucausa Data 20 noiembrie 2011 13:33:35
Problema Ferma2 Scor 100
Compilator cpp Status done
Runda .com 2011 Marime 1.15 kb
#include <algorithm>
#include <cstdio>
using namespace std;

#define INF 0x3f3f3f3f
#define DIM 1005

int v[DIM][DIM],l[DIM][DIM],c[DIM][DIM],d[DIM][DIM],bst[DIM][DIM];
int N,K,cnt,bst_sum;

void read ()
{
    scanf ("%d%d",&N,&K);
    for (int i=1; i<=N; ++i)
        for (int j=1; j<=i; ++j)
        {
            scanf ("%d",&v[i][j]);
            cnt+=v[i][j];
            l[i][j]=v[i][j]+l[i][j-1];
            c[i][j]=v[i][j]+c[i-1][j];
            d[i][j]=v[i][j]+d[i-1][j-1];
        }
}

void solve ()
{
    for (int i=1; i+K<=N; ++i)
        for (int j=1; j<=i; ++j)
            bst[1][1]+=v[i][j];
    for (int i=1; i<=K; ++i)
    {
        bst[i+1][1]=bst[i][1]+l[i+N-K][N-K]-d[i+N-K-1][N-K];
        for (int j=1; j<=i; ++j)
            bst[i+1][j+1]=bst[i+1][j]+c[i][j]-c[i+N-K][j]+d[i+N-K][j+N-K]-d[i][j];
    }
    bst_sum=INF;
    for (int i=1; i<=K+1; ++i)
        for (int j=1; j<=i; ++j)
            bst_sum=min (bst_sum,bst[i][j]);

    printf ("%d",cnt-bst_sum);
}

int main ()
{
    freopen ("ferma2.in","r",stdin);
    freopen ("ferma2.out","w",stdout);

    read ();
    solve ();

    return 0;
}