Cod sursa(job #653029)

Utilizator thesilverhand13FII Florea Toma Eduard thesilverhand13 Data 27 decembrie 2011 05:35:50
Problema Ferma2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
 # include <fstream>
 
 # define dim 1010
 
 using namespace std;

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

 int n, s , k ;
 int a[ dim ][ dim ], sol[ dim ][ dim ], lin[ dim ][ dim ], col[ dim ][ dim ], diag[ dim ][ dim ];
 int solfinal;
 
 void citire()
 {
	 f >> n >> k;
	 for ( int i = 1 ; i <= n ; i ++ )
		 for ( int j = 1 ;j <= i ; ++j )
        {
            f >> a[ i ][ j ] , s+=a[ i ][ j ];
            lin[ i ][ j ] = lin[ i ][ j - 1 ] + a[ i ][ j ];
            col[ i ][ j ] = col[ i - 1 ][ j ] + a[ i ][ j ];
            diag[ i ][ j ] = diag[ i - 1 ][ j -1 ] + a[ i ][ j ];
        }
 }
 
 void rezolva()
 {
	
	int i, j;

	k = n - k;
	
    for( i = 1 ; i <= k ; i ++ )
        for( j = 1 ; j <= i ;j ++)
            sol[ 1 ][ 1 ] += a[ i ][ j ];

    solfinal = sol[ 1 ][ 1 ];

    for ( i = 2 ; i <= n - k + 1 ; i ++ )
    {
        sol[ i ][ 1 ] = sol[ i - 1 ][ 1 ] - diag[ i + k - 2 ][ k ] + lin[ i + k - 1 ][ k ];
        if ( solfinal > sol[ i ][ 1 ] ) 
			solfinal = sol[i][1];
        for ( j = 2 ; j <= i ; ++j )
        {
            sol[ i ][ j ] = sol[ i ][ j - 1 ] + diag[ i + k - 1 ][ j + k - 1 ] - diag[ i - 1 ][ j - 1 ] - ( col[ i + k - 1 ][ j - 1 ] - col[ i - 1 ][ j - 1 ] );
            if ( solfinal > sol[ i ][ j ] ) 
				solfinal = sol[ i ][ j ];
        }
    }

    g << s - solfinal;
 }
 int main()
{
	citire();
	rezolva();
    return 0;
}