Cod sursa(job #1326936)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 26 ianuarie 2015 11:05:14
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.72 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");
long long 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++){
			p = 1;
			u = 9;
			while(p <= u){
				mid = (p + u) / 2;
				if(s[mid] == suma(1, 1, ii1, jj1)){
					break;
				}
				else{
					if(s[mid] > suma(1, 1, ii1, jj1)){
						u = mid - 1;
					}
					else{
						p = mid + 1;
					}
				}
			}
			if(p <= u){
				for(ii2 = ii1 + 1; ii2 < n; ii2++){
					p = 1;
					u = 9;
					while(p <= u){
						mid = (p + u) / 2;
						if(s[mid] == suma(ii1 + 1, 1, ii2, jj1)){
							break;
						}
						else{
							if(s[mid] > suma(ii1 + 1, 1, ii2, jj1)){
								u = mid - 1;
							}
							else{
								p = mid + 1;
							}
						}
					}
					if(p <= u){
						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;
}