# Cod sursa(job #2215824)

Utilizator Data 23 iunie 2018 18:59:57 Ferma2 0 cpp done Arhiva de probleme 2.22 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] ;
}
}
/*for ( i = 1 ; i <= n ; i++ )
{
for ( j = 1 ; j <= i ; j++ )
cout << mat[i][j] << " " ;
cout << endl ;
}
cout << endl ;*/
/*for ( i = 1 ; i <= n ; i++ )
{
for ( j = 1 ; j <= i ; j++ )
cout << lin[i][j] << " " ;
cout << endl ;
}
cout << endl ;
for ( i = 1 ; i <= n ; i++ )
{
for ( j = 1 ; j <= i ; j++ )
cout << col[i][j] << " " ;
cout << endl ;
}
cout << endl ;
for ( i = 1 ; i <= n ; i++ )
{
for ( j = 1 ; j <= i ; j++ )
cout << diag[i][j] << " " ;
cout << endl ;
}
cout << endl ;*/
for ( i = 1 ; i <= kk ; i++ )
sumtr = sumtr + lin[i][i] ;
//cout << sumtr << endl ;
trl = sumtr;
for ( i = 2 ; i <= k+1 ; i++ )
{
sumtr = trl - diag[i][kk] + lin[i+1][kk] ;
trl = sumtr ;
//cout << " pt i " << i << " " << sumtr << endl ;
for ( j = 1 ; j < i ; j++ )
{
//cout << " pt j " << j << " " ;
if ( sumtr < best )
best = sumtr ;
sumtr = sumtr - col[i+1][j] + diag[i+1][j+2] ;
//cout << sumtr << endl ;
}
if ( sumtr < best )
best = sumtr ;
}
fout << sum-best ;
}
``````