Cod sursa(job #2477563)

Utilizator cyber_ghSoltan Gheorghe cyber_gh Data 20 octombrie 2019 17:26:42
Problema Zone Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <bits/stdc++.h>

using namespace std;

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

const int MAXN = 520;
const int Z = 9;
int N, M, K, mat[MAXN][MAXN];
vector<uint64_t> sums(Z);
uint64_t partSum[MAXN][MAXN];

uint64_t getSum(int upperX, int upperY, int lowerX, int lowerY) {
    return  partSum[lowerX][lowerY] - 
            partSum[lowerX][upperY - 1] - 
            partSum[upperX - 1][lowerY] +
            partSum[upperX - 1][upperY - 1];
}



int main() {
    fin >> N;

    for (int i = 0; i < Z; i++) {
        fin >> sums[i];
    }
    sort(sums.begin(), sums.end());

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            fin >> mat[i][j];
            partSum[i][j] = mat[i][j] + partSum[i - 1][j] + partSum[i][j - 1] - partSum[i - 1][j - 1];
        
        }
    }

    for (int l1 = 1; l1 < N; l1++) {
        for (int c1 = 1; c1 < N; c1++) {
            if (find(sums.begin(), sums.end(),getSum(1,1,l1,c1))!=sums.end()) {
                
                for (int l2 = l1 + 1; l2 < N; l2++) {
                    
                    if (find(sums.begin(), sums.end(), getSum(l1 + 1, 1, l2, c1)) != sums.end()) {
                        
                        for (int c2 = c1 + 1; c2 < N; c2++) {
                            // min(9, N * N) * N * min(9, N * N)
                            vector<uint64_t> newSums = {
                                getSum(1,1,l1,c1),              //1
                                getSum(1, c1 + 1, l1, c2),      //2
                                getSum(1, c2 + 1, l1, N),       //3
                                getSum(l1 + 1, 1, l2, c1),      //4
                                getSum(l1 + 1, c1 + 1, l2, c2), //5
                                getSum(l1 + 1, c2 + 1, l2, N),  //6
                                getSum(l2 + 1, 1, N, c1),       //7
                                getSum(l2 + 1, c1 + 1, N, c2),  //8
                                getSum(l2 + 1, c2 + 1, N, N)    //9
                            };            
                            sort(newSums.begin(), newSums.end()) ;
                            if (newSums == sums) {
                                fout << l1 << " " << l2 << " "<< c1 << " "<< c2;
                                return 0;
                            }
                        }
                    }
                }
            }
        }
    }

    return 0;
}