Cod sursa(job #640850)

Utilizator ProcopliucProcopliuc Adrian Procopliuc Data 26 noiembrie 2011 16:39:27
Problema Ferma2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
# include <fstream>
using namespace std;
ifstream f ("ferma2.in");
ofstream g ("ferma2.out");
int s=0,a[1006][1006],smin=1000000000,sum[1005][1005],k,i,j,n,sl[1005][1005],sc[1005][1005];

int main ()
{
	f>>n>>k;
	for (i=1;i<=n;i++)
		for (j=1;j<=i;j++)
		{
			f>>a[i][j];
			sc[i][j]+=sc[i-1][j]+a[i][j];
			sl[i][j]+=sl[i][j-1]+a[i][j];
			s+=a[i][j];
		}
	k=n-k;
	for (i=1;i<=n;i++)
		for (j=1;j<=i;j++)
		{
			if (j<=k)
				sum[i][j]=sum[i-1][j-1]+sl[i][j];
			else			
				sum[i][j]=sum[i-1][j-1]-(sc[i-1][j-k]-sc[i-k-1][j-k])+(sl[i][j]-sl[i][j-k]);
				if (j>=k)
				if (smin>sum[i][j])
					smin=sum[i][j];
			
		}	
	
	g<<s-smin;
	return 0;
}