Cod sursa(job #542524)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 26 februarie 2011 14:30:04
Problema Pixels Scor 40
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 1.48 kb
#include <stdio.h>

int n;
int v[5][15];
int cost[15][15][10];
int sol[15][4100];

inline int max (int a, int b) {return a > b ? a : b;}

int main ()
{
	freopen ("pixels.in", "r", stdin);
	freopen ("pixels.out", "w", stdout);
	
	scanf ("%d", &n);
	
	int i, j, k, ci, cj, bit, c, lim = (1 << n) - 1;
	
	for (i = 1; i <= n; i ++)
		for (j = 1; j <= n; j ++)
			scanf ("%d", &cost[i][j][4]);
	for (i = 1; i <= n; i ++)
		for (j = 1; j <= n; j ++)
			scanf ("%d", &cost[i][j][5]);
	for (i = 1; i <= n; i ++)
		for (j = 1; j <= n; j ++)
			scanf ("%d %d %d %d", &cost[i][j][0], &cost[i][j][1], &cost[i][j][2], &cost[i][j][3]);
	
	for (i = 0; i <= lim; i ++)
	{
		ci = i;
		c = 0;
		
		for (j = 1; j <= n; j ++, ci >>= 1)
		{
			v[1][j] = ci & 1;
			
			c += cost[1][j][v[1][j] + 4];
			c -= cost[1][j][3] * (v[1][j] != v[1][j - 1]);
		}
		sol[1][i] = c;
	}
	
	for (k = 2; k <= n; k ++)
		for (i = 0; i <= lim; i ++)
			for (j = 0; j <= lim; j ++)
			{
				c = 0;
				ci = i;
				cj = j;
				
				for (bit = 1; bit <= n; bit ++, ci >>= 1, cj >>= 1)
				{
					v[1][bit] = ci & 1;
					v[0][bit] = cj & 1;
					
					c += cost[k][bit][v[1][bit] + 4];
					c -= cost[k][bit][3] * (v[1][bit] != v[1][bit - 1]);
					c -= cost[k][bit][0] * (v[1][bit] != v[0][bit]);
				}
				sol[k][i] = max (sol[k][i], sol[k - 1][j] + c);
			}
	
	int solf = -1000000000;
	
	for (i = 0; i <= lim; i ++)
		solf = max (solf, sol[n][i]);
	printf ("%d\n", solf);
	
	return 0;
}