Cod sursa(job #18988)

Utilizator gcosminGheorghe Cosmin gcosmin Data 18 februarie 2007 16:22:55
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

#define NMAX 600
#define LL long long

int N;

LL a[NMAX][NMAX];
LL sum[12];
LL sumlin[NMAX][NMAX];
LL sumcol[NMAX][NMAX];

char viz[12];
LL reg[12];
LL aux[12];

vector <int> saux(4, 0);
vector <int> sol(4, NMAX);

int back(int k)
{
	if (k == 4) {
		int l1, c1, c2, i;

		// gasesc linia
		LL s = 0, ss = reg[1] + reg[2] + reg[3];;
		for (i = 1; i <= N; i++) {
			s += sumlin[i][N];
			if (s == ss) break;
			if (s > ss) return 0;
		}
		if (i == N + 1) return 0;

		l1 = i;
		
		s = 0;
		//gasesc prima coloana
		for (i = 1; i <= N; i++) {
			s += sumcol[l1][i];
			if (s == reg[1]) break;
			if (s > reg[1]) return 0;
		}
		if (i == N + 1) return 0;
		c1 = i;
		//gasesc a doua coloana
		ss = reg[1] + reg[2];
		for (i = i + 1; i <= N; i++) {
			s += sumcol[l1][i];
			if (s == ss) break;
			if (s > ss) return 0;
		}
		if (i == N + 1) return 0;
		c2 = i;

		// gasesc a doua linie (finally) // partea grea

		// fac sumele reg[7], reg[8], reg[9]

		reg[7] = reg[8] = reg[9] = 0;
		for (i = 1; i <= N; i++) {
			if (i <= c1) {
				reg[7] += sumcol[N][i] - sumcol[l1][i];
				continue;
			}
			if (i <= c2) {
				reg[8] += sumcol[N][i] - sumcol[l1][i];
				continue;
			}
			reg[9] += sumcol[N][i] - sumcol[l1][i];
		}

		// baleez :p

		int j;
		reg[4] = reg[5] = reg[6] = 0;
		for (i = l1 + 1; i <= N; i++) {
			reg[4] += sumlin[i][c1];
			reg[7] -= sumlin[i][c1];

			reg[5] += sumlin[i][c2] - sumlin[i][c1];
			reg[8] -= sumlin[i][c2] - sumlin[i][c1];

			reg[6] += sumlin[i][N] - sumlin[i][c2];
			reg[9] -= sumlin[i][N] - sumlin[i][c2];

			memcpy(aux, reg, sizeof(reg));
			sort(aux + 1, aux + 10);

			for (j = 1; j <= 9 && aux[j] == sum[j]; j++);
			
			if (j == 10) {
				saux[0] = l1; saux[1] = c1; saux[2] = i; saux[3] = c2;

				if (saux < sol) sol = saux;
				return 0;
			}
		}
		
		return 0;
	}

	int i;
	for (i = 1; i <= 9; i++)
		if (!viz[i]) {
			reg[k] = sum[i];
			viz[i] = 1;
			if (back(k + 1)) return 1;
			viz[i] = 0;
		}

return 0;
}

int main()
{
	int i, j;
	
	freopen("zone.in", "r", stdin);
	freopen("zone.out", "w", stdout);

	scanf("%d", &N);

	for (i = 1; i <= 9; i++) scanf("%lld", &sum[i]);

	for (i = 1; i <= N; i++) {
		for (j = 1; j <= N; j++) {
			scanf("%lld", &a[i][j]);
			sumlin[i][j] = sumlin[i][j-1] + a[i][j];
			sumcol[i][j] = sumcol[i-1][j] + a[i][j];
		}
	}

	sort(sum + 1, sum + 10);

	back(1);

	printf("%d %d %d %d\n", sol[0], sol[2], sol[1], sol[3]);

fclose(stdin);
fclose(stdout);
return 0;
}