Cod sursa(job #711580)

Utilizator danalex97Dan H Alexandru danalex97 Data 12 martie 2012 13:27:34
Problema Ferma2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
using namespace std;

#define Nmax 1011
#define min(a , b) ( (a < b) ? a : b )
#define oo 1000000011

int N,K;
int A[Nmax][Nmax];
int Sum[Nmax][Nmax];
int Min=oo,Max=0;

void cit()
{
	scanf("%d%d",&N,&K);
	for (int i=1;i<=N;++i)
		for (int j=1;j<=i;++j)
			scanf("%d",&A[i][j]);
}

void make_sum()
{
	for (int i=1;i<=N;++i)
	{
		for (int j=1;j<=i;++j)
			Sum[i][j]=Sum[i][j-1]+A[i][j];
		Max+=Sum[i][i];
	}
}

int main()
{
	freopen("ferma2.in","r",stdin);
	freopen("ferma2.out","w",stdout);
	
	cit();
	make_sum();
	for (int i=N-K;i<=N;++i)
		for (int j=N-K;j<=i;++j)
		{
			int S=0;
			for (int i2=i,j2=j,j3=1;j3<=K;++j3,--j2,--i2)
				S+=Sum[i2][j2]-Sum[i2][j2-(N-K-j3+1)];
			Min=min(S,Min);
		}
	
	printf("%d\n",Max-Min);
	
	return 0;
}