Cod sursa(job #1045211)

Utilizator freak93Adrian Budau freak93 Data 1 decembrie 2013 01:19:47
Problema Zone Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#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";
}