Cod sursa(job #2565895)

Utilizator DragosSDragos Sarbu DragosS Data 2 martie 2020 17:39:51
Problema Ferma2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<bits/stdc++.h>

using namespace std;

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

int a[1001][1001];
int n,k,S;
int l[1001][1001];
int c[1001][1001];
int d[1001][1001];

void citire()
{
    int i,j;

    f>>n>>k;

    for(i=1;i<=n;i++)
        for(j=1;j<=i;j++)
        {
            f>>a[i][j];
            S+=a[i][j];
            l[i][j]=l[i][j-1]+a[i][j];
            c[i][j]=c[i-1][j]+a[i][j];
            d[i][j]=d[i-1][j-1]+a[i][j];
        }
}

int dinamica()
{
    int i,j,s=0,smin,s1,m;

    m=n-k;

    for (i = 1; i <= m; i++)
        s += l[i][i];
    s1=smin=s;
    for(i=m+1;i<=n;i++)
    {
        s=s1=s1+l[i][m]-d[i - 1][m];
        smin=min(smin,s);
        for(j=m+1;j<=i;j++)
        {
            s=s-(c[i][j-m]-c[i-m][j-m])+(d[i][j]-d[i-m][j-m]);
            smin = min(smin, s);
        }
    }
    return S-smin;
}

int main()
{
    citire();
    g<<dinamica()<<"\n";

}