Cod sursa(job #21577)

Utilizator love_for_uSpancioc Riana love_for_u Data 23 februarie 2007 21:14:46
Problema Zone Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.15 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define INF 1000000
#define NMAX 514
#define MMAX 16
#define LGS 9
#define LGC 4

using namespace std;

long long S[NMAX][NMAX];
int CRDS[MMAX], CRDA[MMAX];
long long SM[MMAX], SUM[MMAX];

int N;
int i, j, k, s;
int ii, jj, kk;
int elem;

int comp(long long a[], long long b[], int l)
{
	int r = l, i;
	
	for (i = 1; i <= r; i++)
	{	
		if (a[i] < b[i]) return -1;
		if (a[i] > b[i]) return 1;
	}
		
	return 0;
}

int comp2(int a[], int b[], int l)
{
	int r = l, i;
	
	for (i = 1; i <= r; i++)
	{	
		if (a[i] < b[i]) return -1;
		if (a[i] > b[i]) return 1;
	}
		
	return 0;
}

long long nfsm(int x1, int y1, int x2, int y2)
{
	return (S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1]);
}

int searchC(int left, int right, int x, int y, int crd1, long long SUMA)
{
	int l = left, r = right;
	int crd2 = -INF, c;
	
	while (l <= r)
	{
		c = (l + r)/2;
		
		long long ss = nfsm(x, y, crd1, c);
		
		if (ss > SUMA)  r = c - 1;
		if (ss < SUMA)  l = c + 1;
		if (ss == SUMA) crd2 = c,  r = c - 1;
	}
	
	return crd2;
}

int searchL(int left, int right, int x, int y, int crd2, long long SUMA)
{
	int l = left, r = right;
	int crd1 = -INF, c;
	
	while (l <= r)
	{
		c = (l + r)/2;
		
		long long ss = nfsm(x, y, c, crd2);
		
		if (ss > SUMA)  r = c - 1;
		if (ss < SUMA)  l = c + 1;
		if (ss == SUMA) crd1 = c,  r = c - 1;
	}
	
	return crd1;
}

void solve(int ind1, int ind2, int ind3)
{
	int l1, l2, c1, c2;
	l1 = l2 = c1 = c2 = -INF;
	int i;
	
	memset(SM, 0, sizeof(SM));
	memset(CRDA, 0, sizeof(CRDA));
	
	for (i = 1; i <= N; i++)
	{
		c1 = searchC(1, N, 1, 1, i, SUM[ind1]);
		
		if (c1 != -INF) { l1 = i; break; }
	}
	
	if (l1 != -INF && c1 != -INF)
	{
		SM[1] = SUM[ind1];
		
		c2 = searchC(c1 + 1, N, 1, c1 + 1, l1, SUM[ind2]);
	}
	
	if (c2 != -INF)
	{
		SM[2] = SUM[ind2];
		
		l2 = searchL(l1 + 1, N, l1 + 1, 1, c1, SUM[ind3]);
	}
	
	if (l2 != -INF)
	{
		SM[4] = SUM[ind3];
		
		SM[3] = nfsm(1, c2 + 1, l1, N);
		SM[5] = nfsm(l1 + 1, c1 + 1, l2, c2);
		SM[6] = nfsm(l1 + 1, c2 + 1, l2, N);
		SM[7] = nfsm(l2 + 1, 1, N, c1);
		SM[8] = nfsm(l2 + 1, c1 + 1, N, c2);
		SM[9] = nfsm(l2 + 1, c2 + 1, N, N);
		
		sort(SM + 1, SM + LGS + 1);
	}
	
	if (comp(SM, SUM, LGS) == 0)
	{
		CRDA[1] = l1, CRDA[2] = c1, CRDA[3] = l2, CRDA[4] = c2;
		
		if (comp2(CRDA, CRDS, LGC) == -1) memcpy(CRDS, CRDA, sizeof(CRDA));
	}
		
}

int main()
{
	freopen("zone.in", "r", stdin);
	freopen("zone.out", "w", stdout);
	
	scanf("%d", &N);
	
	for (i = 1; i <= LGS; i++) scanf("%lld", &SUM[i]);
	
	sort(SUM + 1, SUM + LGS + 1);
	
	for (i = 1; i <= N; i++)
	{
		s = 0;
		
		for (j = 1; j <= N; j++)
		{
			scanf("%d", &elem);
			
			s += elem, S[i][j] = S[i-1][j] + s;
		}
	}
	
	for (i = 1; i <= LGC; i++) CRDS[i] = INF;
	
	for (ii = 1; ii <= LGS; ii++)
		for (jj = 1; jj <= LGS; jj++)
			for (kk = 1; kk <= LGS; kk++)
				if (ii != jj && jj != kk && kk != ii) solve(ii, jj, kk);
	
			
	printf("%d ", CRDS[1]);
	printf("%d ", CRDS[3]);
	printf("%d ", CRDS[2]);			
	printf("%d\n", CRDS[4]);
	
	return 0;
}