Cod sursa(job #2486761)

Utilizator Constantin.Dragancea Constantin Constantin. Data 3 noiembrie 2019 14:14:09
Problema Zone Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define N 520
#define fi first
#define se second
ll n, a[N][N], x;
ll dp[N][N], dp2[N][N];
int l1 = N, l2 = N, c1 = N, c2 = N;
vector <ll> sums, aux;
vector <pair<int,int> > poss[2][15];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    ifstream cin ("zone.in");
    ofstream cout ("zone.out");
    cin >> n;
    for (int i=0; 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]){
                    int i = it.fi, j = it.se, i2 = it2.fi - 1, j2 = it2.se - 1;
                    if (i >= i2 || j >= j2) continue;
                    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;
}