Pagini recente » Cod sursa (job #788289) | Cod sursa (job #2820535) | Cod sursa (job #246487) | Cod sursa (job #3166649) | Cod sursa (job #1045211)
#include <iostream>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
using namespace std;
int main() {
ifstream cin("zone.in");
ofstream cout("zone.out");
int N; cin >> N;
array<int64_t, 9> sum;
for (int i = 0; i < 9; ++i)
cin >> sum[i];
vector< vector<int> > V(N, vector<int>(N));
vector< vector<int64_t> > S(N, vector<int64_t>(N));
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j) {
cin >> V[i][j];
S[i][j] = V[i][j];
if (i > 0)
S[i][j] += S[i - 1][j];
if (j > 0)
S[i][j] += S[i][j - 1];
if (i > 0 and j > 0)
S[i][j] -= S[i - 1][j - 1];
}
auto partial = [&](int x1, int y1, int x2, int y2) {
int64_t answer = S[x2][y2];
if (x1 > 0)
answer -= S[x1 - 1][y2];
if (y1 > 0)
answer -= S[x2][y1 - 1];
if (x1 > 0 and y1 > 0)
answer += S[x1 - 1][y1 - 1];
return answer;
};
sort(sum.begin(), sum.end());
vector<int> answer{N, N, N, N};
do {
int L1 = 0, L2 = 0;
while (L1 < N and partial(0, 0, L1, N - 1) < sum[0] + sum[1] + sum[2])
++L1;
L2 = ++L1;
while (L2 < N and partial(L1, 0, L2, N - 1) < sum[3] + sum[4] + sum[5])
++L2;
++L2;
if (L1 >= N or L2 >= N)
continue;
int C1 = 0, C2 = 0;
while (C1 < N and partial(L2, 0, N - 1, C1) < sum[6])
++C1;
C2 = ++C1;
while (C2 < N and partial(L2, C1, N - 1, C2) < sum[7])
++C2;
++C2;
int L[4] = {0, L1, L2, N};
int C[4] = {0, C1, C2, N};
bool ok = true;
for (int i = 0; i < 3; ++i)
for (int j = 0; j < 3; ++j)
if (partial(L[i], C[j], L[i + 1] - 1, C[j + 1] - 1) != sum[i * 3 + j])
ok = false;
if (not ok)
continue;
answer = min<vector<int>>(answer, {L1, C1, L2, C2});
} while (next_permutation(sum.begin(), sum.end()));
cout << answer[0] << " " << answer[2] << " " << answer[1] << " " << answer[3] << "\n";
}