Cod sursa(job #1038519)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 21 noiembrie 2013 17:52:55
Problema Zone Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.14 kb
#include <fstream>
#include <algorithm>

#define maxn 540

using namespace std;

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

long long v[10];
bool mark[10];
long long a[maxn][maxn],s[maxn][maxn];
int n,l1,l2,c1,c2;
int fl1=maxn,fl2=maxn,fc1=maxn,fc2=maxn;

bool check_rest ()
{
    long long r[7];
    r[1] = s[l1][n]-s[l1][c2];
    r[2] = s[l2][c2]-s[l1][c2]-s[l2][c1]+s[l1][c1];
    r[3] = s[l2][n]-s[l2][c2]-s[l1][n]+s[l1][c2];
    r[4] = s[n][c1]-s[l2][c1];
    r[5] = s[n][c2]-s[n][c1]-s[l2][c2]+s[l2][c1];
    r[6] = s[n][n]-s[n][c2]-s[l2][n]+s[l2][c2];

    sort (r+1,r+7);

    for (int i=1,j=1; i<=6 && j<=9; ++j)
    {
        if (mark[j]) continue;
        if (v[j] != r[i]) return 0;
        ++i;
    }

    return 1;
}

void update ()
{
    fl1 = l1;
    fl2 = l2;
    fc1 = c1;
    fc2 = c2;
}

int bs1 (int l, long long x)
{
    int lo = -1, hi = n+1;

    while (hi - lo > 1)
    {
        int mid = (lo+hi)/2;
        if (s[l][mid] >= x)
            hi = mid;
        else lo = mid;
    }

    if (s[l][hi] != x || hi==n+1) return 0;
    return hi;
}

int bs2 (int c, long long x)
{
    int lo = -1, hi = n+1;

    while (hi - lo > 1)
    {
        int mid = (lo+hi)/2;
        if (s[mid][c] >= x)
            hi = mid;
        else lo = mid;
    }

    if (s[hi][c] != x || hi==n+1) return 0;
    return hi;
}

int main()
{
    freopen ("zone.in","r",stdin);

    scanf ("%d",&n);

    for (int i=1; i<=9; ++i)
    {
        scanf ("%I64d",&v[i]);
    }

    sort (v+1,v+10);

    for (int i=1; i<=n; ++i)
        for (int j=1; j<=n; ++j)
            scanf ("%I64d",&a[i][j]);

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


    for (l1=1; l1<=n-2; ++l1)
    {
        for (int i=1; i<=9; ++i)
        {
            mark[i] = 1;

            c1 = bs1 (l1,v[i]);
            if (!c1)
            {
               mark[i]=0;
               continue;
            }

            for (int j=1; j<=9; ++j)
            {
                if (mark[j]) continue;
                mark[j] = 1;

                c2 = bs1 (l1,v[i]+v[j]);
                if (!c2)
                {
                    mark[j]=0;
                    continue;
                }

                for (int k=1; k<=9; ++k)
                {
                    if (mark[k]) continue;
                    mark[k] = 1;

                    l2 = bs2 (c1,v[i]+v[k]);
                    if (!l2)
                    {
                        mark[k]=0;
                        continue;
                    }

                    if (check_rest())
                    {
                        if (l1 < fl1) update();
                        else if (l2 < fl2) update();
                        else if (c1 < fc1) update ();
                        else if (c2 < fc2) update ();
                    }

                    mark[k] = 0;
                }

                mark[j] = 1;
            }

            mark[i] = 1;
        }
    }

    fout<<fl1<<" "<<fl2<<" "<<fc1<<" "<<fc2;
}