Pagini recente » Cod sursa (job #2480269) | Cod sursa (job #1869446) | Cod sursa (job #1162507) | Cod sursa (job #273434) | Cod sursa (job #2480702)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define N 520
int a[N][N],i,j,n,pvm[9];
long long l[N],c[N],fms[9],s[N][N];
pair<pair<int,int>,pair<int,int> >ans;
vector <int>v[N];
int bsl (long long x){
int p = 0;
for (int it = n; it > 0; it >>= 1)
while (it + p < n && s[p + it][n - 1] <= x)
p += it;
return p;
}
int bsc (long long x){
int p = 0;
for (int it = n; it > 0; it >>= 1)
while (it + p < n && s[n - 1][p + it] <= x)
p += it;
return p;
}
bool reusit (){
int l1,l2,c1,c2;
l1 = bsl (fms[pvm[0]] + fms[pvm[1]] + fms[pvm[2]]);
l2 = bsl (fms[pvm[0]] + fms[pvm[1]] + fms[pvm[2]] + fms[pvm[3]] + fms[pvm[4]] + fms[pvm[5]]);
c1 = bsc (fms[pvm[0]] + fms[pvm[3]] + fms[pvm[6]]);
c2 = bsc (fms[pvm[0]] + fms[pvm[3]] + fms[pvm[6]] + fms[pvm[1]] + fms[pvm[4]] + fms[pvm[8]]);
if (fms[pvm[0]] == s[l1][c1] &&
fms[pvm[3]] == s[l2][c1] - s[l1][c1] &&
fms[pvm[6]] == s[n - 1][c1] - s[l2][c1] &&
fms[pvm[1]] == s[l1][c2] - s[l1][c1] &&
fms[pvm[2]] == s[l1][n - 1] - s[l1][c2] &&
fms[pvm[4]] == s[l2][c2] - s[l1][c2] - s[l2][c1] + s[l1][c1] &&
fms[pvm[5]] == s[l2][n - 1] - s[l2][c2] - s[l1][n - 1] + s[l1][c2] &&
fms[pvm[7]] == s[n - 1][c2] - s[l2][c2] - s[n - 1][c1] + s[l2][c1] &&
fms[pvm[8]] == s[n - 1][n - 1] - s[n - 1][c2] - s[l2][n - 1] + s[l2][c2]){
pair<pair<int,int>,pair<int,int> >curr(make_pair(l1,c1),make_pair(l2,c2));
ans = min(ans,curr);
}
}
void bkt (int k,int mask){
if (mask + 1 == (1 << 9)){
reusit ();
return;
}
for (int i = 0; i < v[mask].size(); ++i){
pvm[k] = v[mask][i];
bkt(k + 1, mask + (1 << v[mask][i]));
pvm[k] = 0;
}
}
int main()
{
ifstream fin ("zone.in");
ofstream fout ("zone.out");
fin >> n;
for (i = 0; i < 511; ++i)
for (j = 0; j < 9; ++j)
if (!(i & (1 << j)))
v[i].push_back (j);
for (i = 0; i < 9; ++i)
fin >> fms[i];
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j){
fin >> a[i][j];
l[i] += a[i][j];
c[j] += a[i][j];
if (i > 0 && j > 0)
s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j];
else{
if (i + j < 1)
s[i][j] = a[i][j];
if (i > 0)
s[i][j] = a[i][j] + s[i - 1][j];
if (j > 0)
s[i][j] = a[i][j] + s[i][j - 1];
}
}
for (i = 0; i <= n; ++i){
s[i][n] = s[i][n - 1] + 1;
s[n][i] = s[n - 1][i] + 1;
}
ans = make_pair(make_pair(N,N),make_pair(N,N));
bkt (0,0);
fout << ans.first.first + 1 << " " << ans.second.first + 1 << " " << ans.first.second + 1 << " " << ans.second.second + 1;
return 0;
}