Cod sursa(job #3339739)

Utilizator Radu_BicliBiclineru Radu Radu_Bicli Data 9 februarie 2026 19:14:10
Problema Zone Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <bits/stdc++.h>

using namespace std;

#define USE_STD_IO 0
#if USE_STD_IO
    #define fin cin
    #define fout cout
#else
    ifstream fin("zone.in");
    ofstream fout("zone.out");
#endif

int n, i, j, ii, jj, mars[522][522], s;
int sume[12];
int viz[12];

static inline int Sum(int i, int j, int ii, int jj) {
    return mars[ii][jj] - mars[ii][j - 1] - mars[i - 1][jj] + mars[i - 1][j - 1];
}

static inline int InVec(int el) {
    for(int i = 1; i <= 9; i++) {
        if(sume[i] == el && !viz[i]) return i;
    }
    return -1;
}

static inline bool Verif(int l1, int c1, int l2, int c2) {
    vector<int> lin = {0, l1, l2, n};
    vector<int> col = {0, c1, c2, n};

    for(int i = 1; i <= 9; i++) viz[i] = false;

    for(int i = 1; i <= 3; i++) {
        for(int j = 1; j <= 3; j++) {
            s = Sum(lin[i - 1] + 1, col[j - 1] + 1, lin[i], col[j]);
            int poz = InVec(s);

            if(-1 == poz) return false;
            if(viz[poz]) return false;
            viz[poz] = true;
        }
    }

    return true;
}

int main() {
    if(USE_STD_IO) ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

    fin >> n;
    for(i = 1; i <= 9; i++) fin >> sume[i];
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= n; j++) {
            fin >> mars[i][j];
            mars[i][j] += mars[i - 1][j] + mars[i][j - 1] - mars[i - 1][j - 1];
        }
    }

    for(i = 1; i <= n; i++) {
        for(j = 1; j <= n; j++) {
            s = Sum(1, 1, i, j);
            for(int i = 1; i <= 9; i++) viz[i] = false;
            if(-1 == InVec(s)) continue;

            for(ii = i + 1; ii <= n; ii++) {
                for(jj = j + 1; jj <= n; jj++) {
                    if(Verif(i, j, ii, jj)) {
                        fout << i << ' ' << ii << ' ' << j << ' ' << jj;
                        return 0;
                    }
                }
            }
        }
    }

    return 0;
}