Cod sursa(job #2910244)

Utilizator euyoTukanul euyo Data 18 iunie 2022 19:04:09
Problema Zone Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin( "zone.in" );
ofstream fout( "zone.out" );

const int DIM = 520;
const int NZ = 9; 

int sum[NZ + 1];
int a[DIM][DIM];
int v[NZ + 1];
bool use[NZ + 1];

int S[DIM][DIM];
int lin[DIM];
int col[DIM];

int n;
int l1 = 1e9, c1 = 1e9, l2 = 1e9, c2 = 1e9;

int bsl( int val ) {
  int st = 0, dr = n;

  while ( dr - st > 1 ) {
	int mid = (st + dr) / 2;
	if ( lin[mid] < val ) {
	  st = mid;
	} else {
	  dr = mid;
	}
  }
  if ( lin[st] == val ) return st;
  if ( lin[dr] == val ) return dr;
  return -1;
}
int bsc( int val ) {
  int st = 0, dr = n;

  while ( dr - st > 1 ) {
	int mid = (st + dr) / 2;
	if ( col[mid] < val ) {
	  st = mid;
	} else {
	  dr = mid;
	}
  }
  if ( col[st] == val ) return st;
  if ( col[dr] == val ) return dr;
  return -1;
}

/*void solve() {
  int zl1 = bsl( v[1] + v[2] + v[3] );
  int zc1 = bsc( v[1] + v[4] + v[7] );
  int zl2 = bsl( v[1] + v[2] + v[3] + v[4] + v[5] + v[6] );
  int zc2 = bsc( v[1] + v[4] + v[7] + v[2] + v[5] + v[8] );
  if ( zl1 == -1 || zl2 == -1 || zc1 == -1 || zc2 == -1 ) return;
  if ( l1 > zl1 ) {
	l1 = zl1, l2 = zl2, c1 = zc1, c2 = zc2;
  } else if ( l1 == zl1 ) {
	if ( c1 > zc1 ) {
	  l1 = zl1, l2 = zl2, c1 = zc1, c2 = zc2;
	} else if ( c1 == zc1 ) {
	  if ( l2 > zl2 ) {
		l1 = zl1, l2 = zl2, c1 = zc1, c2 = zc2;
	  } else if ( l2 == zl2 ) {
		if ( c2 > zc2 ) {
		  l1 = zl1, l2 = zl2, c1 = zc1, c2 = zc2;
		}
	  }
	}
  }
}*/

void solve() {
  return;
}

void perm( int i ) {
  if ( i == NZ + 1 ) {
	solve();
	return;
  }
  for ( int j = 1; j <= NZ; ++j ) {
	if ( !use[j] ) {
	  use[j] = true;
	  v[i] = sum[j];
	  perm( i + 1 );
	  use[j] = false;
	}
  }
}

int main() {
  fin >> n;
  for ( int i = 1; i <= NZ; ++i ) fin >> sum[i];
  for ( int i = 1; i <= n; ++i ) {
	int s = 0;
	for ( int j = 1; j <= n; ++j ) {
	  fin >> a[i][j];
	  S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + a[i][j];
	  s += a[i][j];
	}
    lin[i] = lin[i - 1] + s;
  }
  for ( int j = 1; j <= n; ++j ) {
	int s = 0;
	for ( int i = 1; i <= n; ++i ) {
	  s += a[i][j];
	}
	col[j] = col[j - 1] + s;
  }
  perm(1);
  fout << l1 << " " << l2 << " " << c1 << " " << c2 << "\n";
  fin.close();
  fout.close();
  return 0;
}