Pagini recente » Cod sursa (job #899560) | Cod sursa (job #2133202) | Cod sursa (job #742260) | Cod sursa (job #427446) | Cod sursa (job #18988)
Cod sursa(job #18988)
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
#define NMAX 600
#define LL long long
int N;
LL a[NMAX][NMAX];
LL sum[12];
LL sumlin[NMAX][NMAX];
LL sumcol[NMAX][NMAX];
char viz[12];
LL reg[12];
LL aux[12];
vector <int> saux(4, 0);
vector <int> sol(4, NMAX);
int back(int k)
{
if (k == 4) {
int l1, c1, c2, i;
// gasesc linia
LL s = 0, ss = reg[1] + reg[2] + reg[3];;
for (i = 1; i <= N; i++) {
s += sumlin[i][N];
if (s == ss) break;
if (s > ss) return 0;
}
if (i == N + 1) return 0;
l1 = i;
s = 0;
//gasesc prima coloana
for (i = 1; i <= N; i++) {
s += sumcol[l1][i];
if (s == reg[1]) break;
if (s > reg[1]) return 0;
}
if (i == N + 1) return 0;
c1 = i;
//gasesc a doua coloana
ss = reg[1] + reg[2];
for (i = i + 1; i <= N; i++) {
s += sumcol[l1][i];
if (s == ss) break;
if (s > ss) return 0;
}
if (i == N + 1) return 0;
c2 = i;
// gasesc a doua linie (finally) // partea grea
// fac sumele reg[7], reg[8], reg[9]
reg[7] = reg[8] = reg[9] = 0;
for (i = 1; i <= N; i++) {
if (i <= c1) {
reg[7] += sumcol[N][i] - sumcol[l1][i];
continue;
}
if (i <= c2) {
reg[8] += sumcol[N][i] - sumcol[l1][i];
continue;
}
reg[9] += sumcol[N][i] - sumcol[l1][i];
}
// baleez :p
int j;
reg[4] = reg[5] = reg[6] = 0;
for (i = l1 + 1; i <= N; i++) {
reg[4] += sumlin[i][c1];
reg[7] -= sumlin[i][c1];
reg[5] += sumlin[i][c2] - sumlin[i][c1];
reg[8] -= sumlin[i][c2] - sumlin[i][c1];
reg[6] += sumlin[i][N] - sumlin[i][c2];
reg[9] -= sumlin[i][N] - sumlin[i][c2];
memcpy(aux, reg, sizeof(reg));
sort(aux + 1, aux + 10);
for (j = 1; j <= 9 && aux[j] == sum[j]; j++);
if (j == 10) {
saux[0] = l1; saux[1] = c1; saux[2] = i; saux[3] = c2;
if (saux < sol) sol = saux;
return 0;
}
}
return 0;
}
int i;
for (i = 1; i <= 9; i++)
if (!viz[i]) {
reg[k] = sum[i];
viz[i] = 1;
if (back(k + 1)) return 1;
viz[i] = 0;
}
return 0;
}
int main()
{
int i, j;
freopen("zone.in", "r", stdin);
freopen("zone.out", "w", stdout);
scanf("%d", &N);
for (i = 1; i <= 9; i++) scanf("%lld", &sum[i]);
for (i = 1; i <= N; i++) {
for (j = 1; j <= N; j++) {
scanf("%lld", &a[i][j]);
sumlin[i][j] = sumlin[i][j-1] + a[i][j];
sumcol[i][j] = sumcol[i-1][j] + a[i][j];
}
}
sort(sum + 1, sum + 10);
back(1);
printf("%d %d %d %d\n", sol[0], sol[2], sol[1], sol[3]);
fclose(stdin);
fclose(stdout);
return 0;
}