Cod sursa(job #21321)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 23 februarie 2007 12:05:06
Problema Zone Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <cstdio>
#include <cstring>

const int NMAX = 524;
const int SMAX = 9;

int N, sl1 = NMAX, sc1 = NMAX, sl2, sc2;
long long S[SMAX];
long long L[NMAX][NMAX], C[NMAX][NMAX];

inline long long suma(long long A[NMAX][NMAX], int l1, int c1, int l2, int c2) {
	return A[l2][c2] - A[l2][c1] - A[l1][c2] + A[l1][c1];
}

void read() {
	FILE *fin = fopen("zone.in", "rt");
	int i, j;

	fscanf(fin, " %d", &N);

	for (i = 0; i < SMAX; ++i)
		fscanf(fin, " %lld", S + i);
	
	for (i = 1; i <= N; ++i)
		for (j = 1; j <= N; ++j) {
			
			fscanf(fin, " %lld", &L[i][j]);

			L[i][j] += L[i - 1][j] + L[i][j - 1] - L[i - 1][j - 1];
			C[j][i] = L[i][j];
		}

	fclose(fin);
}

int b_search(long long A[NMAX], long long sum) {
	int i, pas, t;

	for (pas = 1; pas <= N; pas <<= 1);

	for (i = 1; pas > 0; pas >>= 1)
		if ((t = i + pas) <= N)
			if (A[t] <= sum)
				i += pas;

	return A[i] == sum ? i : -1;
}

bool check(int l1, int c1, int l2, int c2) {
	bool V[SMAX], ok;
	int l[4] = {0, l1, l2, N};
	int c[4] = {0, c1, c2, N};
	int i, j, k;
	long long s;

	memset(V, 0x00, sizeof(V));

	for (i = 0; i < 3; ++i)
		for (j = 0; j < 3; ++j) {
			s = suma(L, l[i], c[j], l[i + 1], c[j + 1]);

			for (ok = true, k = 0; k < SMAX && ok; ++k)
				if (V[k] == false && S[k] == s)
					V[k] = true, ok = false;

			if (ok) return false;
		}
	
	return true;
}

// Ma chinui si eu degeaba...
// Ce cod aiurea
void get_in_the_zone() {
	int i, j, k;
	int l1, l2, c1, c2;

	for (i = 0; i < SMAX && sl1 == NMAX; ++i) {
		
		for (l1 = 1; l1 < N && sl1 == NMAX; ++l1) {
			c1 = b_search(L[l1], S[i]);

			if (c1 != -1) {

				for (j = 0; j < SMAX; ++j)
					if (j != i) {
						l2 = b_search(C[c1], S[i] + S[j]);

						if (l2 != -1) {
							
							for (k = 0; k < SMAX; ++k)
								if (k != i && k != j) {
									c2 = b_search(L[l1], S[i] + S[k]);

									if (c2 != -1 && check(l1, c1, l2, c2)) 
										if (c1 < sc1 || (c1 == sc1 && l2 < sl2) || (c1 == sc1 && l2 == sl2 && c2 < sc2)) {
											sl1 = l1; sl2 = l2;
											sc1 = c1; sc2 = c2;
										}
								}

						}
					}

			}
		}
	}
}

void write() {
	FILE *fout = fopen("zone.out", "wt");

	fprintf(fout, "%d %d %d %d\n", sl1, sl2, sc1, sc2);

	fclose(fout);
}

int main() {

	read();

	get_in_the_zone();

	write();
	
	return 0;
}