Cod sursa(job #972854)

Utilizator marius135Dumitran Adrian Marius marius135 Data 12 iulie 2013 19:45:10
Problema Zone Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.77 kb
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>

using namespace std;

#define maxn 514

set<int> my_sums;
vector < pair<int, int> > lines, columns;
int mat[maxn][maxn], sum_lin[maxn], sum_col[maxn], sum_par_lin[maxn], sum_par_col[maxn];
int n;
int sum_mat[maxn][maxn], nr[maxn];


void citire(){

	cin>>n;
	
	for( int i = 0; i <= 8; ++i)
		cin>>nr[i];
	sort( nr, nr + 9);
	for( int i = 1; i <= n; ++i) 
		for( int j = 1; j <= n; ++j) {
			cin>> mat[i][j];
			sum_lin[i] += mat[i][j];
			sum_col[j] += mat[i][j];
			sum_mat[i][j] = sum_mat[i][j-1] + sum_col[j];
		}
	
	for( int i = 1; i <= n; ++i) {
		sum_par_lin[i] = sum_par_lin[i-1] + sum_lin[i];
		sum_par_col[i] = sum_par_col[i-1] + sum_col[i];
	}
	
	

}

int calc_sum( int x1, int y1, int x2, int y2){
	
	return sum_mat[x1-1][y1-1] + sum_mat[x2][y2] - sum_mat[ x1-1][y2] - sum_mat[ x2][y1-1];
}

int main() {
	
	freopen("zone.in", "r", stdin);
	freopen("zone.out", "w", stdout);
	
	citire();
	
	for( int i = 0; i < 8; ++i)
		for( int j = i + 1; j < 9; ++j)
			for( int k = j + 1; k < 9; ++k) {
				int new_sum = nr[i] + nr[j] + nr[k];
				my_sums.insert(new_sum);
			}
	
	for( int i = 1; i < n; ++i)
		for( int j = i + 1; j < n; ++j){
			int sum1 = sum_par_lin[i];
			int sum2 = sum_par_lin[j] - sum_par_lin[i];
			int sum3 = sum_par_lin[n] - sum_par_lin[j];
			if( my_sums.find(sum1) != my_sums.end() && my_sums.find(sum2) != my_sums.end() && my_sums.find(sum3) != my_sums.end()) {
				lines.push_back( make_pair(i,j));
			}
		}
	for( int i = 1; i < n; ++i)
		for( int j = i + 1; j < n; ++j){
			int sum1 = sum_par_col[i];
			int sum2 = sum_par_col[j] - sum_par_col[i];
			int sum3 = sum_par_col[n] - sum_par_col[j];
			if( my_sums.find(sum1) != my_sums.end() && my_sums.find(sum2) != my_sums.end() && my_sums.find(sum3) != my_sums.end()) {
				columns.push_back( make_pair(i,j));
			}
		}
	for( size_t i = 0; i < lines.size(); ++i)
		for( size_t j = 0; j < columns.size(); ++j) {
			int sums[9];
			int l1 = lines[i].first, l2 = lines[i].second;
			int c1 = columns[j].first, c2 = columns[j].second;
			
			sums[0] = calc_sum( 1, 1, l1, c1);
			sums[1] = calc_sum( 1, c1 + 1, l1, c2);
			sums[2] = calc_sum( 1, c2 + 1, l1, n);
			sums[3] = calc_sum( l1 + 1, 1, l2, c1);
			sums[4] = calc_sum( l1 + 1, c1 + 1, l2, c2);
			sums[5] = calc_sum( l1 + 1, c2 + 1, l2, n);
			sums[6] = calc_sum( l2 + 1, 1, n, c1);
			sums[7] = calc_sum( l2 + 1, c1 + 1, n, c2);
			sums[8] = calc_sum( l2 + 1, c2 + 1, n, n);
			sort( sums, sums + 9);
			int ok = 1;
			for( int i = 0; i <= 8; ++i)
				if( sums[i] != nr[i]) {
					ok = 0;
					break;
				}
			if( ok == 1) {
				cout<<l1<<" "<<l2<<" "<<c1<<" "<<c2<<endl;
				return 0;
			}
		}
	
	return 0;
}