Cod sursa(job #2080015)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 2 decembrie 2017 12:06:50
Problema Ferma2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <cstdio>
#include <iostream>

using namespace std;
int a[1001][1001],sv[1001][1001],so[1001][1001],sd[1001][1001],d[1001][1001];
int main()
{
    FILE *fin=fopen ("ferma2.in","r");
    FILE *fout=fopen ("ferma2.out","w");
    int n,k,s,i,j,l,sol;
    fscanf(fin,"%d%d",&n,&k);
    s=0;
    for (i=1;i<=n;i++)
        for (j=1;j<=i;j++){
            fscanf (fin,"%d",&a[i][j]);
            s+=a[i][j];
            sv[i][j]=sv[i-1][j]+a[i][j];
            so[i][j]=so[i][j-1]+a[i][j];
            sd[i][j]=sd[i-1][j-1]+a[i][j];
        }
    //calculez normal d[1][1]
    l=n-k;
    for (i=1;i<=l;i++)
        for (j=1;j<=i;j++)
            d[1][1]+=a[i][j];
    sol=d[1][1];
    for (i=2;i+l-1<=n;i++){
        // cand j=1 calculez pe d[i][j] din d[i-1][j]
        j=1;
        d[i][j]=d[i-1][j]-(sd[i+l-2][j+l-1]-sd[i-2][j-1])+so[i+l-1][j+l-1];
        sol=min (sol,d[i][j]);
        for (j=2;j<=i;j++){
            // il calculez pe d[i][j] din d[i][j-1]
            d[i][j]=d[i][j-1]-(sv[i+l-1][j-1]-sv[i-1][j-1])+(sd[i+l-1][j+l-1]-sd[i-1][j-1]);
            sol=min(sol,d[i][j]);
        }
    }
    fprintf (fout,"%d",s-sol);
    return 0;
}