# Cod sursa(job #2215965)

Utilizator Data 24 iunie 2018 13:57:41 Ferma2 100 cpp done Arhiva de probleme 1.46 kb
``````#include <bits/stdc++.h>
#define N 1005

using namespace std;

ifstream fin("ferma2.in") ;
ofstream fout("ferma2.out") ;

int mat[N][N] , lin[N][N] , col[N][N] , diag[N][N] , sump[N][N] ;

int main()
{
int n , k , i , j , sum = 0 , kk , sumtr = 0 , trl = 0 , best = 0x3f3f3f3f ;
fin >> n >> k ;
kk = n-k;
for ( i = 1 ; i <= n ; i++ )
{
for ( j = 1 ; j <= i ; j++ )
{
fin >> mat[i][j] ;
sum += mat[i][j] ;
col[i][j] = col[i-1][j] + mat[i][j] ;
lin[i][j] = mat[i][j] + lin[i][j-1] ;
diag[i][j] = diag[i-1][j-1] + mat[i][j] ;
if ( j > kk )
lin[i][j] = lin[i][j] - mat[i][j-kk] ;
if ( i > kk )
col[i][j] = col[i][j] - mat[i-kk][j] ;
if ( i > kk && j > kk )
diag[i][j] = diag[i][j] - mat[i-kk][j-kk] ;
}
}
best = sum ;
for ( i = 1 ; i <= kk ; i++ )
sumtr = sumtr + lin[i][i] ;
trl = sumtr;
if ( sumtr < best )
best = sumtr ;
for ( i = 2 ; i <= k+1 ; i++ )
{
sumtr = trl - diag[i+kk-2][kk] + lin[i+kk-1][kk] ;
trl = sumtr ;
for ( j = 1 ; j < i ; j++ )
{
if ( sumtr < best )
best = sumtr ;
sumtr = sumtr - col[i+kk-1][j] + diag[i+kk-1][j+kk] ;
}
if ( sumtr < best )
best = sumtr ;
}
fout << sum-best ;
}
``````