Pagini recente » Cod sursa (job #74027) | Cod sursa (job #2323727) | Cod sursa (job #977500) | Cod sursa (job #1920416) | Cod sursa (job #590127)
Cod sursa(job #590127)
#include <cstdlib>
#include <fstream>
#include <algorithm>
using namespace std;
typedef long long i64;
i64 N, Z[10];
i64 A[515][515];
i64 S[512][512];
i64 Val[10], Sv[10];
inline i64 sum(int i1, int j1, int i2, int j2)
{
return S[i2][j2] - S[i1 - 1][j2] - S[i2][j1 - 1] + S[i1 - 1][j1 - 1];
}
int main()
{
ifstream fin("zone.in");
ofstream fout("zone.out");
fin >> N;
for (int i = 1; i <= 9; ++i)
fin >> Z[i];
for (int i = 1; i <= N; ++i)
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];
}
// 81 * N^2 log^2 N
int step;
for (step = 1; (step << 1) <= N; step <<= 1);
for (int first = 1; first <= 9; ++first)
for (int l1 = 1; l1 <= N - 2; ++l1)
{
int nstep1 = step, c1;
for (c1 = N - 1; nstep1; nstep1 >>= 1)
if (c1 - nstep1 >= 1 && S[l1][c1 - nstep1] >= Z[first])
c1 -= nstep1;
for (int second = 1; second <= 9; ++second)
if (first != second)
{
Sv[0] = 0;
for (int k = 1; k <= 9; ++k)
if (k != first && k != second)
Sv[++Sv[0]] = Z[k];
sort(Sv + 1, Sv + Sv[0] + 1);
for (int l2 = l1 + 2; l2 <= N; ++l2)
{
int nstep2 = step, c2;
for (c2 = N; nstep2; nstep2 >>= 1)
if (c2 - nstep2 >= c1 + 2 && sum(l2, c2 - nstep2, N, N) >= Z[second])
c2 -= nstep2;
// Primul si ultimul sunt obtinute sigur
Val[0] = 0;
Val[++Val[0]] = sum(1, c1 + 1, l1, c2 - 1);
Val[++Val[0]] = sum(1, c2, l1, N);
Val[++Val[0]] = sum(l1 + 1, 1, l2 - 1, c1);
Val[++Val[0]] = sum(l1 + 1, c1 + 1, l2 - 1, c2 - 1);
Val[++Val[0]] = sum(l1 + 1, c2, l2 - 1, N);
Val[++Val[0]] = sum(l2, 1, N, c1);
Val[++Val[0]] = sum(l2, c1 + 1, N, c2 - 1);
sort(Val + 1, Val + Val[0] + 1);
bool ok = true;
for (int i = 1; i <= Sv[0]; ++i)
if (Sv[i] != Val[i])
{
ok = false;
break;
}
if (ok)
{
fout << l1 << ' ' << l2 - 1 << ' ' << c1 << ' ' << c2 - 1 << '\n';
fin.close();
fout.close();
exit(0);
}
}
}
}
fin.close();
fout.close();
}