Cod sursa(job #543807)

Utilizator cont_de_testeCont Teste cont_de_teste Data 28 februarie 2011 16:58:57
Problema Pixels Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <stdio.h>
#include <string.h>

#define NMAX 111

int A[NMAX][NMAX], B[NMAX][NMAX], C[NMAX][NMAX][4];
int color[NMAX][NMAX];
int i, j, k, N, ii, jj, profit, max_improvement, improvement;

void read_input_data() {
	freopen("pixels.in", "r", stdin);
	scanf("%d", &N);
	for (i = 1; i <= N; i++)
		for (j = 1; j <= N; j++)
			scanf("%d", &A[i][j]);

	for (i = 1; i <= N; i++)
		for (j = 1; j <= N; j++)
			scanf("%d", &B[i][j]);

	for (i = 1; i <= N; i++)
		for (j = 1; j <= N; j++)
			for (k = 0; k < 4; k++)
				scanf("%d", &C[i][j][k]);
}

void greedy() {
	memset(color, 0, sizeof(color));

	profit = 0;
	for (i = 1; i <= N; i++)
		for (j = 1; j <= N; j++)
			if (A[i][j] > B[i][j]) {
				color[i][j] = 0;
				profit += A[i][j];
			} else {
				color[i][j] = 1;
				profit += B[i][j];
			}

	for (i = 1; i <= N; i++)
		for (j = 1; j <= N; j++) {
			if (color[i][j] != color[i - 1][j])
				profit -= C[i][j][0];
			if (color[i][j] != color[i][j - 1])
				profit -= C[i][j][3];
		}

	while (1) {
		//fprintf(stderr, "profit=%d\n", profit);

		max_improvement = 0;
		for (i = 1; i <= N; i++)
			for (j = 1; j <= N; j++) {
				if (color[i][j] == 0)
					improvement = B[i][j] - A[i][j];
				else
					improvement = A[i][j] - B[i][j];

				if (color[i][j] != color[i - 1][j])
					improvement += C[i][j][0];
				else
					improvement -= C[i][j][0];

				if (color[i][j] != color[i][j + 1])
					improvement += C[i][j][1];
				else
					improvement -= C[i][j][1];

				if (color[i][j] != color[i + 1][j])
					improvement += C[i][j][2];
				else
					improvement -= C[i][j][2];

				if (color[i][j] != color[i][j - 1])
					improvement += C[i][j][3];
				else
					improvement -= C[i][j][3];

				if (improvement > max_improvement) {
					max_improvement = improvement;
					ii = i;
					jj = j;
				}
			}

		if (max_improvement > 0) {
			color[ii][jj] = 1 - color[ii][jj];
			profit += max_improvement;
		} else {
			break;
		}
	}
}

int main() {
	read_input_data();
	greedy();

	freopen("pixels.out", "wt", stdout);
	printf("%d\n", profit);

	return 0;
}