Cod sursa(job #2987738)

Utilizator rares89_Dumitriu Rares rares89_ Data 2 martie 2023 19:07:34
Problema Zone Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("zone.in");
ofstream fout("zone.out");

int n, a[12], v[515][515], l[5], c[5], viz[12];
long long int sp[515][515];

long long int suma(int is, int js, int ij, int jj) {
    return sp[ij][jj] - sp[is][jj] - sp[ij][js] + sp[is][js];
}

inline int pozInVector(long long int x) {
    for(int i = 1; i <= 9; i++) {
        if(!viz[i] && a[i] == x) {
            return i;
        }
    }
    return 0;
}

inline bool valid(int l1, int c1, int l2, int c2) {
    l[1] = l1, c[1] = c1, l[2] = l2, c[2] = c2;
    l[3] = c[3] = n;
    // verific toate sumele partiale
    for(int i = 1; i <= 3; i++) {
        for(int j = 1; j <= 3; j++) {
            int ind = pozInVector(suma(l[i - 1], c[j - 1], l[i], c[j]));
            if(ind == 0 || viz[ind]) { // daca aceasta val a fost deja folosita
                return false;
            }
            viz[ind] = true;
        }
    }
    return true;
}

int main() {
    fin >> n;
    for(int i = 1; i <= 9; i++) {
        fin >> a[i];
    }
    sort(a + 1, a + 10);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            fin >> v[i][j];
            sp[i][j] = sp[i - 1][j] + sp[i][j - 1] - sp[i - 1][j - 1] + 1LL * v[i][j];
        }
    }
    bool gasit = false;
    for(int i = 1; i < n && !gasit; i++) {
        for(int j = 1; j < n && !gasit; j++) {
            if(pozInVector(sp[i][j])) { // verific daca suma curenta se afla in vector
                for(int k = i + 1; k < n && !gasit; k++) {
                    for(int l = j + 1; l < n && !gasit; l++) {
                        gasit = valid(i, j, k, l);
                        // resetez viz (in care marchez daca o zona a fost gasita)
                        for(int ii = 1; ii <= 9; ii++) {
                            viz[ii] = 0;
                        }
                    }
                }
            }
        }
    }
    fout << l[1] << " " << l[2] << " " << c[1] << " " << c[2];
    return 0;
}