Pagini recente » Cod sursa (job #2029229) | Cod sursa (job #222796) | Cod sursa (job #3247044) | Cod sursa (job #583544) | Cod sursa (job #2486752)
#include <bits/stdc++.h>
using namespace std;
#define N 520
#define fi first
#define se second
int n, a[N][N], dp[N][N], dp2[N][N];
int l1 = N, l2 = N, c1 = N, c2 = N;
vector <int> sums, aux;
vector <pair<int,int> > poss[2][15];
int main(){
freopen("zone.in", "r", stdin);
freopen("zone.out", "w", stdout);
cin >> n;
for (int i=0, x; i<9; i++) cin >> x, sums.push_back(x);
sort(sums.begin(), sums.end());
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++) cin >> a[i][j];
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++) dp[i][j] = a[i][j] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
for (int i=n; i; i--)
for (int j=n; j; j--) dp2[i][j] = a[i][j] + dp2[i+1][j] + dp2[i][j+1] - dp2[i+1][j+1];
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
for (int idx=0; idx<9; idx++){
if (dp[i][j] == sums[idx]) poss[0][idx].push_back({i, j});
if (dp2[i][j] == sums[idx]) poss[1][idx].push_back({i, j});
}
for (int k1=0; k1<9; k1++){
for (int k2=0; k2<9; k2++){
if (k1 == k2) continue;
for (auto it: poss[0][k1]){
for (auto it2: poss[1][k2]){
if (it.fi >= it2.fi - 1 || it.se >= it2.se - 1) continue;
int i = it.fi, j = it.se, i2 = it2.fi - 1, j2 = it2.se - 1;
aux.clear();
aux.push_back(dp[i][j]);
aux.push_back(dp[i][j2] - dp[i][j]);
aux.push_back(dp[i][n] - dp[i][j2]);
aux.push_back(dp[i2][j] - dp[i][j]);
aux.push_back(dp[i2][j2] - dp[i][j2] - dp[i2][j] + dp[i][j]);
aux.push_back(dp[i2][n] - dp[i2][j2] - dp[i][n] + dp[i][j2]);
aux.push_back(dp[n][j] - dp[i2][j]);
aux.push_back(dp[n][j2] - dp[n][j] - dp[i2][j2] + dp[i2][j]);
aux.push_back(dp[n][n] - dp[n][j2] - dp[i2][n] + dp[i2][j2]);
sort(aux.begin(), aux.end());
if (aux == sums){
if (l1 == i && c1 == j && l2 == i2 && j2 < c2) c2 = j2;
else if (l1 == i && c1 == j && i2 < l2) l2 = i2, c2 = j2;
else if (l1 == i && j < c1) c1 = j, l2 = i2, c2 = j2;
else if (i < l1) l1 = i, c1 = j, l2 = i2, c2 = j2;
}
}
}
}
}
cout << l1 << ' ' << l2 << ' ' << c1 << ' ' << c2;
return 0;
}