Pagini recente » Cod sursa (job #1808645) | Cod sursa (job #2863824) | Cod sursa (job #1818350) | Cod sursa (job #953434) | Cod sursa (job #1038520)
#include <fstream>
#include <algorithm>
#define maxn 540
using namespace std;
ifstream fin("zone.in");
ofstream fout("zone.out");
long long v[10];
bool mark[10];
long long a[maxn][maxn],s[maxn][maxn];
int n,l1,l2,c1,c2;
int fl1=maxn,fl2=maxn,fc1=maxn,fc2=maxn;
bool check_rest ()
{
long long r[7];
r[1] = s[l1][n]-s[l1][c2];
r[2] = s[l2][c2]-s[l1][c2]-s[l2][c1]+s[l1][c1];
r[3] = s[l2][n]-s[l2][c2]-s[l1][n]+s[l1][c2];
r[4] = s[n][c1]-s[l2][c1];
r[5] = s[n][c2]-s[n][c1]-s[l2][c2]+s[l2][c1];
r[6] = s[n][n]-s[n][c2]-s[l2][n]+s[l2][c2];
sort (r+1,r+7);
for (int i=1,j=1; i<=6 && j<=9; ++j)
{
if (mark[j]) continue;
if (v[j] != r[i]) return 0;
++i;
}
return 1;
}
void update ()
{
fl1 = l1;
fl2 = l2;
fc1 = c1;
fc2 = c2;
}
int bs1 (int l, long long x)
{
int lo = -1, hi = n+1;
while (hi - lo > 1)
{
int mid = (lo+hi)/2;
if (s[l][mid] >= x)
hi = mid;
else lo = mid;
}
if (s[l][hi] != x || hi==n+1) return 0;
return hi;
}
int bs2 (int c, long long x)
{
int lo = -1, hi = n+1;
while (hi - lo > 1)
{
int mid = (lo+hi)/2;
if (s[mid][c] >= x)
hi = mid;
else lo = mid;
}
if (s[hi][c] != x || hi==n+1) return 0;
return hi;
}
int main()
{
freopen ("zone.in","r",stdin);
scanf ("%d",&n);
for (int i=1; i<=9; ++i)
{
scanf ("%lld",&v[i]);
}
sort (v+1,v+10);
for (int i=1; i<=n; ++i)
for (int j=1; j<=n; ++j)
scanf ("%lld",&a[i][j]);
for (int i=1; i<=n; ++i)
for (int j=1; j<=n; ++j)
s[i][j] = a[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1];
for (l1=1; l1<=n-2; ++l1)
{
for (int i=1; i<=9; ++i)
{
mark[i] = 1;
c1 = bs1 (l1,v[i]);
if (!c1)
{
mark[i]=0;
continue;
}
for (int j=1; j<=9; ++j)
{
if (mark[j]) continue;
mark[j] = 1;
c2 = bs1 (l1,v[i]+v[j]);
if (!c2)
{
mark[j]=0;
continue;
}
for (int k=1; k<=9; ++k)
{
if (mark[k]) continue;
mark[k] = 1;
l2 = bs2 (c1,v[i]+v[k]);
if (!l2)
{
mark[k]=0;
continue;
}
if (check_rest())
{
if (l1 < fl1) update();
else if (l2 < fl2) update();
else if (c1 < fc1) update ();
else if (c2 < fc2) update ();
}
mark[k] = 0;
}
mark[j] = 0;
}
mark[i] = 0;
}
}
fout<<fl1<<" "<<fl2<<" "<<fc1<<" "<<fc2;
}