Cod sursa(job #636363)

Utilizator swift90Ionut Bogdanescu swift90 Data 19 noiembrie 2011 19:21:02
Problema Ferma2 Scor 100
Compilator cpp Status done
Runda .com 2011 Marime 0.76 kb
#include<cstdio>
#include<fstream>
using namespace std;
int nr[1010][1010],sumv[1010][1010],sumd[1010][1010];
int N,K,S;
int main(){
	//freopen("ferma2.in","r",stdin);
	ifstream f("ferma2.in");
	freopen("ferma2.out","w",stdout);
	int i,j,min=1000000000,ax,k;
	f>>N>>K;
	for(i=1;i<=N;++i){
		for(j=1;j<=i;++j){
			f>>nr[i][j];
			sumv[i][j]=sumv[i-1][j]+nr[i][j];
			sumd[i][j]=sumd[i-1][j-1]+nr[i][j];
			S+=nr[i][j];
		}
	}
	K=N-K;
	for(i=K;i<=N;++i){
		ax=0;
		for(k=1;k<=K;++k)
			ax+=sumv[i][k]-sumv[i-K+k-1][k];
		if(ax<min)
			min=ax;
		for(j=2;j+K<=i+1;++j){
			ax-=sumv[i][j-1]-sumv[i-K][j-1];
			ax+=sumd[i][j+K-1]-sumd[i-K][j-1];
			if(ax<min)
				min=ax;
		}
	}
	
	printf("%d\n",S-min);
	fclose(stdin);
	fclose(stdout);
	return 0;
}