Cod sursa(job #547884)

Utilizator ooctavTuchila Octavian ooctav Data 6 martie 2011 19:43:27
Problema Pixels Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<deque>
#include<queue>
#include<set>
#include<vector>
using namespace std;

const char IN[] = {"pixels.in"};
const char OUT[] = {"pixels.out"};
const int INF = 1000000005;
const double PI  = 3.14159265;
const int NMAX = 10;
const int lin[] = {-1, 0, 1, 0};
const int col[] = {0, 1, 0, -1};

#define II inline
#define LL long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define FOR(i, a, b) 	for(int i = a ; i <= b ; i++)
#define IFOR(i, a, b) 	for(int i = a ; i >= b ; i--)
#define FORIT(it, V) 	for(vector<int> :: iterator it = V.begin() ; it != V.end() ; it++)
#define all(a) a, a + 

int N;
int cost[NMAX + 1][1<<NMAX + 1];
int a[NMAX + 1][NMAX + 1], b[NMAX + 1][NMAX + 1], c[NMAX + 1][NMAX + 1][4];
int S;
int bit[NMAX + 1];
int l;

void citi()
{
	scanf("%d", &N);
	FOR(i, 1, N)
		FOR(j, 1, N)
			scanf("%d", &a[i][j]);
	FOR(i, 1, N)
		FOR(j, 1, N)
			scanf("%d", &b[i][j]);
	FOR(i, 1, N)
		FOR(j, 1, N)
			FOR(k, 0, 3)
				scanf("%d", &c[i][j][k]);
}

int afla_cost(int x, int l)
{
	int s = 0, pas = 1<<(N - 1);
	for(int i = 1 ; i <= N ; i++, pas >>= 1)
	{
		if(x & pas)	s += a[l][i];
		else		s += b[l][i];
		if(i > 1 && (((x & pas) && !(x & pas<<1)) || (!(x & pas) && (x & pas<<1))))
			s -= c[l][i][3];
	}
	return s;
}

int scad(int x)
{
	int s = 0, pas = 1<<(N - 1);
	for(int i = 1 ; i <= N ; i++, pas >>= 1)
		if(x & pas)
			s += c[l][i][0];
	return s;
}

void obt_sol()
{
	FOR(x, 0, (1<<N) - 1)
	{
		cost[l][x] = -INF;
		int S = afla_cost(x, l);
		
		if(l == 1)
		{
			cost[l][x] = S;
			continue;
		}
		
		FOR(i, 0, (1<<N) - 1)
		{
			if(cost[l - 1][i] + S - scad(i^x) > cost[l][x])
				cost[l][x] = cost[l - 1][i] + S - scad(i^x);
		}
	}
}

void scrie()
{
	int maxim = 0;
	FOR(i, 0, (1<<N) - 1)
		maxim = max(maxim, cost[N][i]);
	printf("%d\n", maxim);
}

int main()
{
	freopen(IN, "r", stdin);
	freopen(OUT, "w", stdout);
	citi();
	for(l = 1 ; l <= N ; l++)
		obt_sol();
	scrie();
	return 0;
}