Pagini recente » Cod sursa (job #351969) | Cod sursa (job #511310) | Cod sursa (job #2819790) | Cod sursa (job #358024) | Cod sursa (job #2987738)
#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;
}