Cod sursa(job #3339742)

Utilizator Radu_BicliBiclineru Radu Radu_Bicli Data 9 februarie 2026 19:17:44
Problema Zone Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.07 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

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

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

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

static inline bool Verif(long long l1, long long c1, long long l2, long long c2) {
    vector<long long> lin = {0, l1, l2, n};
    vector<long long> 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);
            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;
                    }
           	    for(int i = 1; i <= 9; i++) viz[i] = false;
                }
            }
        }
    }

    return 0;
}