Cod sursa(job #551886)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 11 martie 2011 11:50:17
Problema Zone Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <fstream>
#include <algorithm>
using namespace std;
#define DIM 514
#define INF (1 << 28) - 1

ifstream f ("zone.in");
ofstream g ("zone.out");

int N, A[DIM][DIM], P[DIM][DIM], S[11], R[11], L1, L2, C1, C2, l1, l2, c1, c2;

int compa ()
{
	for (int i = 1; i <= 9; i++)
		if (R[i] != S[i])
			return 0;
	if (l2 >= L2)
		return 0;
	if (l1+l2+c1+c2 >= L1+L2+C1+C2)
		return 0;
	return 1;
}

int main (){
	int i, j;
	
	f >> N;
	for (i = 1; i <= 9; i++)
		f >> S[i];
	sort (S + 1, S + 10);
	for (i = 1; i <= N; i++)
		for (j = 1; j <= N; j++)
		{
			f >> A[i][j];
			P[i][j] = A[i][j] + P[i-1][j] + P[i][j-1] - P[i-1][j-1];			
		}
	
	L1 = L2 = C1 = C2 = INF;
	for (l1 = 1; l1 <= N - 2; l1++)
		for (l2 = l1 + 1; l2 <= N - 1; l2++)
			for (c1 = 1; c1 <= N - 2; c1++)
				for (c2 = c1 + 1; c2 <= N - 1; c2++)
				{
					R[1] = P[l1][c1];
					R[2] = P[l2][c1] - R[1];
					R[3] = P[N][c1] - R[2] - R[1];
					R[4] = P[l1][c2] - R[1];
					R[5] = P[l2][c2] - R[1] - R[2] - R[4];
					R[6] = P[N][c2] - R[1] - R[2] - R[3] - R[4] - R[5];
					R[7] = P[l1][N] - R[1] - R[4];
					R[8] = P[l2][N] - R[1] - R[2] - R[4] - R[5] - R[7];
					R[9] = P[N][N] - R[1] - R[2] - R[3] - R[4] - R[5] - R[6] - R[7] - R[8];
					sort (R + 1, R + 10);
					if ( compa () )
					{
						L1 = l1, L2 = l2;
						C1 = c1, C2 = c2;
					}
				}

	g << L1 << ' ' << L2 << ' ' << C1 << ' ' << C2;
	return 0;
}