Cod sursa(job #1694556)

Utilizator sucureiSucureiRobert sucurei Data 25 aprilie 2016 16:38:16
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.56 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin ("zone.in");
ofstream fout ("zone.out");
struct art { int sol1, sol2, sol3, sol4; } aux;
int N, l1, c1, l2, c2, V[530][530];
long long V9[10], b[10], S[530][530];
vector < art > A;

bool Caut_Binar(long long val)
{
    int st = 1, dr = 9, mij;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (V9[mij] < val) st = mij + 1;
        else if (V9[mij] > val) dr = mij - 1;
        else return 1;
    }
    return 0;
}

long long Sum(int i1, int j1, int i2, int j2)
{
    return (S[i1-1][j1-1] + S[i2][j2] - S[i1-1][j2] - S[i2][j1-1]);
}

bool cmp(art a, art b)
{
    if (a.sol1 < b.sol1) return 1;
    else if (a.sol1 > b.sol1) return 0;
    if (a.sol3 < b.sol3) return 1;
    else if (a.sol3 > b.sol3) return 0;
    if (a.sol2 < b.sol2) return 1;
    else if (a.sol2 > b.sol2) return 0;
    if (a.sol1 + a.sol2 + a.sol3 + a.sol4 < b.sol1 + b.sol2 + b.sol3 + b.sol4) return 1;
    return 0;
}

bool Verif()
{
    if (!Caut_Binar(Sum(1, 1, l1, c1))) return 0;
    else b[1] = Sum(1, 1, l1, c1);

    if (!Caut_Binar(Sum(1, c1+1, l1, c2))) return 0;
    else b[2] = Sum(1, c1+1, l1, c2);

    if (!Caut_Binar(Sum(1, c2+1, l1, N))) return 0;
    else b[3] = Sum(1, c2+1, l1, N);

    if (!Caut_Binar(Sum(l1+1, 1, l2, c1))) return 0;
    else b[4] = Sum(l1+1, 1, l2, c1);

    if (!Caut_Binar(Sum(l1+1, c1+1, l2, c2))) return 0;
    else b[5] = Sum(l1+1, c1+1, l2, c2);

    if (!Caut_Binar(Sum(l1+1, c2+1, l2, N))) return 0;
    else b[6] = Sum(l1+1, c2+1, l2, N);

    if (!Caut_Binar(Sum(l2+1, 1, N, c1))) return 0;
    else b[7] = Sum(l2+1, 1, N, c1);

    if (!Caut_Binar(Sum(l2+1, c1+1, N, c2))) return 0;
    else b[8] = Sum(l2+1, c1+1, N, c2);

    if (!Caut_Binar(Sum(l2+1, c2+1, N, N))) return 0;
    else b[9] = Sum(l2+1, c2+1, N, N);

    sort (b + 1, b + 10);
    for (int i = 1; i <= 9; i++)
    {
        if (b[i] != V9[i]) return 0;
    }
    return 1;
}

int main()
{
    fin >> N;
    for (int i = 1; i <= 9; i++) fin >> V9[i];
    sort (V9 + 1, V9 + 10);
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            fin >> V[i][j];
            S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + V[i][j];
        }
    }

    for (int i = 1; i < N - 1; i++)
    {
        for (int j = 1; j < N - 1; j++)
        {
            if (Caut_Binar(S[i][j]))
            {
                l1 = i, c1 = j;
                for (int k = i + 1; k < N; k++)
                {
                    if (Caut_Binar(Sum(i+1, 1, k, j)))
                    {
                        l2 = k;
                        for (int k = j + 1; k < N; k++)
                        {
                            if (Caut_Binar(Sum(1, j+1, i, k)))
                            {
                                c2 = k;
                                if (Verif())
                                {
                                    aux.sol1 = l1;
                                    aux.sol2 = l2;
                                    aux.sol3 = c1;
                                    aux.sol4 = c2;
                                    A.push_back(aux);
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    sort (A.begin(), A.end(), cmp);
    fout << A.front().sol1 << ' ' << A.front().sol2 << ' ' << A.front().sol3 << ' ' << A.front().sol4 << '\n';
    fout.close();
    return 0;
}