Cod sursa(job #22593)

Utilizator mockeBarca Cristian Mihai mocke Data 26 februarie 2007 21:00:45
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.22 kb
//100p

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define INF 2000000000
#define NMAX 524
#define MMAX 10
#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 ((long long)(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 ind4)
{
	int l1, l2, c1, c2, i;
	l1 = l2 = c1 = c2 = -INF;
		
	for (i = 1; i <= LGS; i++) SM[i] = -INF;
	for (i = 1; i <= LGC; i++) CRDA[i] = +INF;

	for (i = 1; i <= N - 3; i++)
	{
		l1 = l2 = c1 = c2 = -INF;
		
		c1 = searchC(1, N - 3, 1, 1, i, SUM[ind1]);
		
		if (c1 != -INF) l1 = i; 
	
	
		if (l1 != -INF && c1 != -INF)
		{
			SM[1] = SUM[ind1];
		
			c2 = searchC(c1 + 1, N - 2, 1, c1 + 1, l1, SUM[ind2]);
		}
	
		if (c2 != -INF)
		{
			SM[2] = SUM[ind2];
		
			l2 = searchL(l1 + 1, N - 2, l1 + 1, 1, c1, SUM[ind4]);
		}
	
		if (l2 != -INF)
		{
			SM[4] = SUM[ind4];
		
			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) < 0) 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 %d %d %d\n", CRDS[1], CRDS[3], CRDS[2], CRDS[4]);
		
	return 0;
}