Cod sursa(job #2477255)

Utilizator flibiaVisanu Cristian flibia Data 19 octombrie 2019 21:35:10
Problema Zone Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.66 kb
#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;

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

int n, v[10], a[600][600], dp[2][600][600];
vector<pair<int, int> > can[2][10];
vector<int> fx, aux;
vector<pair<pair<int, int>, pair<int, int> > > sol;

int main() {
    in >> n;
    for (int i = 1; i <= 9; i++) 
        in >> v[i], fx.push_back(v[i]);

    sort(v + 1, v + 10);
    sort(fx.begin(), fx.end());

    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= n; j++)
            in >> a[i][j];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dp[0][i][j] = a[i][j] + dp[0][i - 1][j] + dp[0][i][j - 1] - dp[0][i - 1][j - 1];

    for (int i = n; i > 0; i--)
        for (int j = n; j > 0; j--)
            dp[1][i][j] = a[i][j] + dp[1][i + 1][j] + dp[1][i][j + 1] - dp[1][i + 1][j + 1];



    for (int k = 1; k <= 9; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                if (dp[0][i][j] == v[k])
                    can[0][k].push_back({i, j});
                if (dp[1][i][j] == v[k])   
                    can[1][k].push_back({i, j});
            }

    for (int k1 = 1; k1 <= 9; k1++)
        for (int k2 = 1; k2 <= 9; k2++) {
            if (k1 == k2)
                continue;

            for (auto it : can[0][k1])
                for (auto it2 : can[1][k2]) {
                    if (it2.fi < it.fi + 2 || it2.se < it.se + 2)
                        continue;

                    int x = it.fi, y = it.se, xx = it2.fi, yy = it2.se;
                    aux.clear();
                    aux.push_back(dp[0][x][y]);
                    aux.push_back(dp[0][x][yy - 1] - dp[0][x][y]);
                    aux.push_back(dp[0][x][n] - dp[0][x][yy - 1]);
                    aux.push_back(dp[0][xx - 1][y] - dp[0][x][y]);
                    aux.push_back(dp[0][xx - 1][yy - 1] - dp[0][xx - 1][y] - dp[0][x][yy - 1] + dp[0][x][y]);
                    aux.push_back(dp[0][xx - 1][n] - dp[0][xx - 1][yy - 1] - dp[0][x][n] + dp[0][x][yy - 1]);
                    aux.push_back(dp[1][xx][yy]);
                    aux.push_back(dp[1][xx][y + 1] - dp[1][xx][yy]);
                    aux.push_back(dp[1][xx][1] - dp[1][xx][y + 1]);
                    
                    sort(aux.begin(), aux.end());
 
                    if (aux == fx) 
                        sol.push_back(make_pair(make_pair(x, xx - 1), make_pair(y, yy - 1)));
                }        
        }

    sort(sol.begin(), sol.end());
    out << sol[0].fi.fi << ' ' << sol[0].fi.se << ' ' << sol[0].se.fi << ' ' << sol[0].se.se;
    return 0;
}