Cod sursa(job #1326928)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 26 ianuarie 2015 10:51:04
Problema Zone Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include<fstream>
#include<algorithm>
using namespace std;
int n, i, j, p, u, mid, l1, l2, c1, c2, ii1, ii2, jj1, jj2, ok, k;
long long a[515][515], b[515][515], s[10], s1[10];
ifstream fin("zone.in");
ofstream fout("zone.out");
int suma(int x, int y, int z, int t){
	return b[z][t] - b[x-1][t] - b[z][y-1] + b[x-1][y-1]; 
}
int main(){
	fin>> n;
	for(i = 1; i <= 9; i++){
		fin>> s[i];
	}
	sort(s + 1, s + 10);
	l1 = l2 = c1 = c2 = 1000;
	for(i = 1; i <= n; i++){
		for(j = 1; j <= n; j++){
			fin>> a[i][j];
			b[i][j] = a[i][j] + b[i-1][j] + b[i][j-1] - b[i-1][j-1];
		}
	}
	for(ii1 = 1; ii1 < n - 1; ii1++){
		for(jj1 = 1; jj1 < n - 1; jj1++){
			for(ii2 = ii1 + 1; ii2 < n; ii2++){
				for(jj2 = jj1 + 1; jj2 < n; jj2++){

					s1[1]=suma(1, 1, ii1, jj1);
					s1[2]=suma(ii1 + 1, 1, ii2, jj1);
					s1[3]=suma(ii2 + 1, 1, n, jj1);
					s1[4]=suma(1, jj1+1, ii1, jj2);
					s1[5]=suma(ii1 + 1, jj1 + 1, ii2, jj2);
					s1[6]=suma(ii2 + 1, jj1+1, n, jj2);
					s1[7]=suma(1, jj2 + 1, ii1, n);
					s1[8]=suma(ii1 + 1 ,jj2 + 1, ii2, n);
					s1[9]=suma(ii2 + 1,jj2 + 1, n, n);
					sort(s1 + 1, s1 + 10);
					ok = 1;
					for(int ii = 1; ii <= 9; ii++){
						if(s1[ii] != s[ii]){
							ok = 0;
							break;
						}
					}
					if(ok == 1){
						if(ii1 < l1){
							l1 = ii1;
							c1 = jj1;
							l2 = ii2;
							c2 = jj2;
						}
						else{
							if(ii1 == l1){
								if(c1 > jj1){
									l1 = ii1;
									c1 = jj1;
									l2 = ii2;
									c2 = jj2;
								}
								else{
									if(c1 == jj1){
										if(l2 > ii2){
											l1 = ii1;
											c1 = jj1;
											l2 = ii2;
											c2 = jj2;
										}
										else{
											if(l2 == ii2){
												if(c2 > jj2){
													l1 = ii1;
													c1 = jj1;
													l2 = ii2;
													c2 = jj2;
												}
											}
										}
									}
								}
							}
						}
					}
				}
			}
		}
	}
	fout<< l1 <<" "<< l2 <<" "<< c1 <<" "<< c2 <<"\n";
	return 0;
}