Cod sursa(job #2480330)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 25 octombrie 2019 12:47:02
Problema Zone Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.13 kb
#include <fstream>
#include <vector>
#include <iostream>
#include <algorithm>
#define nmax 520
using namespace std;
ifstream f("zone.in");
ofstream g("zone.out");
vector <int> l_var, c_var;

int a[10], b[10], c[10], uz[10];
int v[nmax][nmax], l1s = nmax, l2s, c1s, c2s, n;
long long s[nmax][nmax];


int findin(int k, int a1, int a2, int p[])
{
    for (int i = a1; i <= a2; i++)
        if (p[i] == k)
            return true;
    return false;
}
bool ok(int l1, int c1, int l2, int c2)
{
    int i;
    c[1] = s[l1][c1];
    c[2] = s[l1][c2] - c[1];
    c[3] = s[l1][n] - c[1] - c[2];

    c[4] = s[l2][c1] - c[1];
    c[5] = s[l2][c2] - c[1] - c[2] - c[4];
    c[6] = s[l2][n] - c[1] - c[2] - c[3] - c[4] - c[5];

    c[7] = s[n][c1] - c[1] - c[4];
    c[8] = s[n][c2] - c[1] - c[2] - c[4] - c[5] - c[7];
    c[9] = s[n][n] - c[1] - c[2] - c[3] - c[4] - c[5] - c[6] - c[7] - c[8];

    /*
    cout << l1 << ' ' <<  l2  << ' ' << c1 << ' ' << c2 << '\n';
    if (l1 == 1 && c1 == 2) {
        for (i = 1; i <= 9; i++)
            cout << c[i] << ' ';
        cout << '\n';
    }*/

    sort (c + 1 , c + 10);

    for (i = 1; i <= 9; i++)
        if (a[i] != c[i])
            return false;
    return true;
}
void verif_permutation(int p[])
{
    int l1 = 1, c1 = 1, l2 , c2;
    while (c1 + 2 < n && s[1][c1 + 1] <= p[1])
        c1 ++;
    for (; l1 + 2 < n;) {
        c_var.clear();
        l_var.clear();

        if (s[l1][c1] == p[1]) {
            for (c2 = c1 + 1; c2 < n; c2 ++)
                if (findin(s[l1][c2] - s[l1][c1], 2, 9, p))
                    c_var.push_back(c2);

            for (l2 = l1 + 1; l2 < n; l2 ++)
                if (findin(s[l2][c1] - s[l1][c1], 2, 9, p))
                    l_var.push_back(l2);
        }

        for (int i = 0; i < c_var.size(); i++)
            for (int j  = 0; j < l_var.size(); j++) {
                c2 = c_var[i];
                l2 = l_var[j];
                if (ok(l1, c1, l2, c2)) {
                    if (l1 < l1s || (l1 == l1s && l2 < l2s) || (l1 == l1s && l2 == l2s && c1 + c2 < c1s + c2s)) {
                        l1s = l1;
                        l2s = l2;
                        c1s = c1;
                        c2s = c2;
                    }
                }

            }
        l1 ++;
        while (c1 > 1 && s[l1][c1] > p[1])
            c1--;
    }

}
int main()
{
    int i, j;
    f >> n;
    for (i = 1; i <= 9; i++)
        f >> a[i];

    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            f >> v[i][j];

    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + 1LL * v[i][j];
    /*
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++)
            cout << s[i][j] << ' ';
        cout << '\n';
    }*/

    for (i = 1; i <= 9; i++)
        b[i] = a[i];

    sort(a + 1, a + 10);

    for (i = 1; i <= 9; i++) {
        swap(b[1], b[i]);
        verif_permutation(b);
        swap(b[i], b[1]);
    }

    g << l1s << ' ' << l2s << ' ' << c1s << ' ' << c2s << '\n';


    return 0;
}