Cod sursa(job #613683)

Utilizator cezar305Mr. Noname cezar305 Data 3 octombrie 2011 22:27:13
Problema Ferma2 Scor Ascuns
Compilator cpp Status done
Runda Marime 0.95 kb
#include <stdio.h>

int n, k, sol, suma;
int v[1002][1002], sp[1002][1002], spc[1002][1002], spl[1002][1002];

int main ()
{
	freopen ("ferma2.in", "r", stdin);
	freopen ("ferma2.out", "w", stdout);
	
	scanf ("%d %d", &n, &k);
	
	int i, j, st, dr, s, x, y;
	
	for (i = 1; i <= n; i ++)
		for (j = 1; j <= i; j ++)
		{
			scanf ("%d", &v[i][j]);
			sp[i - j][j] = sp[i - j][j - 1] + v[i][j];
			spl[i][j] = spl[i][j - 1] + v[i][j];
			spc[i][j] = spc[i - 1][j] + v[i][j];
		}
	
	for (x = 1; x <= k + 1; x ++)
	{
		s = 0;
		for (i = 1; i < x; i ++)
			s += spc[n][i];
		y = k - x + 1;
		for (i = 0; i < y; i ++)
			s += sp[i][n - i] - sp[i][x - 1];
		if (s > sol)
			sol = s;
		
		st = x + 1;
		dr = st + (n - k) - 1;
		for (j = 1; j <= y; j ++)
		{
			s = s + spl[n - j + 1][dr] - spl[n - j + 1][st - 1];
			s = s - sp[y - j][dr] - sp[y - j][st - 1];
			if (s > sol)
				sol = s;
		}
	}
	
	printf ("%d\n", sol);
	return 0;
}