Cod sursa(job #1741703)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 14 august 2016 20:16:56
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <fstream>
#include <cmath>
#include <vector>
#include <iomanip>
#include <queue>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_set>
#include <set>
#include <map>
using namespace std;

const int MAXN = 512;

long long sum[10], a[1 + MAXN][1 + MAXN];
bool seen[10];

void Erase(long long value) {
    for (int i = 1; i <= 9; i++)
        if (sum[i] == value && seen[i]) {
            seen[i] = false;
            return;
        }
}

bool Set(long long value) {
    for (int i = 1; i <= 9; i++)
        if (sum[i] == value && !seen[i]) {
            seen[i] = true;
            return true;
        }
    return false;
}

long long Sum(int l1, int c1, int l2, int c2) {
    return a[l2][c2] - a[l1 - 1][c2] - a[l2][c1 - 1] + a[l1 - 1][c1 - 1];
}

void Solve(int n, int &l1, int &c1, int &l2, int &c2) {
    for (l1 = 1; l1 < n; l1++)
        for (c1 = 1; c1 < n; c1++)
            if (Set(Sum(1, 1, l1, c1))) {
                for (l2 = l1 + 1; l2 <= n; l2++)
                    if (Set(Sum(l1 + 1, 1, l2, c1))) {
                        if (Set(Sum(l2 + 1, 1, n, c1))) {
                            for (c2 = c1 + 1; c2 <= n; c2++) {
                                if (Set(Sum(l1 + 1, c1 + 1, l2, c2))) {
                                    if (Set(Sum(1, c2 + 1, l1, n)))
                                        return;
                                    Erase(Sum(l1 + 1, c1 + 1, l2, c2));
                                }
                            }
                            Erase(Sum(l2 + 1, 1, n, c1));
                        }
                        Erase(Sum(l1 + 1, 1, l2, c1));
                    }
                Erase(Sum(1, 1, l1, c1));
            }
}

int main() {
    ifstream cin("zone.in");
    ofstream cout("zone.out");
    int n;
    cin >> n;
    for (int i = 1; i <= 9; i++)
        cin >> sum[i];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
            a[i][j] = a[i][j] + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
        }
    int l1, c1, l2, c2;
    Solve(n, l1, c1, l2, c2);
    cout << l1 << " " << l2 << " " << c1 << " " << c2;
    return 0;
}