Cod sursa(job #94182)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 21 octombrie 2007 21:09:35
Problema Zone Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.37 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define NMAX ((1<<9)+10)

int N, V[12], A[NMAX][NMAX], S[NMAX][NMAX], L[NMAX][12];
int L1, L2, C1, C2, v[12], x[12];

void read()
{
        int i, j;

        freopen("zone.in", "r", stdin);
        scanf("%d", &N);
        for (i = 1; i < 10; i++) scanf("%d", V+i), v[i-1] = V[i];
        sort(v,v+9);
        for (i = 1; i <= N; i++)
        {
            for (j = 1; j <= N; j++)
            {
                scanf("%d", &A[i][j]);
                S[i][j] = S[i][j-1]+A[i][j];
            }
            for (j = 1; j <= N; j++) S[i][j] += S[i-1][j];
        }
}

int search(int l, int l1, int c1, int a, int b, int x)
{
        int p = a, q = b, md, s;

        while (p<=q)
        {
                md = (p+q)>>1; s = x+S[l1][md]-S[l1][c1];
                if (S[l][md]==s) return md;
                if (s<S[l][md]) q = md-1;
                else p = md+1;
        }
        return -1;
}

void solve()
{
        int k, i, j, l1, l2, c1, c2, s, ok;

        for (k = 1; k < 11; k++)
            for (i = 1; i <= N; i++)
                for (j = 1; j <= N; j++)
                    if (S[i][j]==V[k]) L[i][k] = j;

        L1 = L2 = C1 = C2 = 666;
        for (i = 1; i < 11; i++)
            for (j = 1; j < 11; j++)
                if (i!=j)
                   for (l1 = 1; l1 <= N; l1++)
                       if (L[l1][i]>0)
                       {
                             c1 = L[l1][i];
                             for (l2 = l1+1; l2 <= N; l2++)
                             {
                                s = V[j]+S[l2][c1];
                                c2 = search(l2,l1,c1,c1+1,N,s);
                                if (c2>c1)
                                {
                                      x[0] = S[l1][c1];
                                      x[1] = S[l1][c2]-S[l1][c1];
                                      x[2] = S[l1][N]-S[l1][c2];
                                      x[3] = S[l2][c1]-S[l1][c1];
                                      x[4] = S[l2][c2]-S[l1][c2]-S[l2][c1]+S[l1][c1];
                                      x[5] = S[l2][N]-S[l2][c2]-S[l1][N]+S[l1][c2];
                                      x[6] = S[N][c1]-S[l2][c1];
                                      x[7] = S[N][c2]-S[N][c1]-S[l2][c2]+S[l2][c1];
                                      x[8] = S[N][N]-S[l2][N]-S[N][c2]+S[l2][c2];

                                      sort(x,x+9);
                                      for (k = 0, ok = 1; k < 10 && ok; k++)
                                          if (v[k]!=x[k]) ok = 0;
                                      if (ok)
                                         if ( (L1>l1)||( (l1==L1)&&((L1+C1)>(l1+c1)) )||( ((l1+c1)==(L1+C1))&&((L1+C1+L2)>(l1+c1+l2)) )||( ((l1+c1+l2)==(L1+C1+L2))&&((L1+C1+L2+C2)>(l1+c1+l2+c2)) ) )
                                         {
                                                L1 = l1; L2 = l2;
                                                C1 = c1; C2 = c2;
                                         }
                                }
                             }
                       }
}

void write()
{
        freopen("zone.out", "w", stdout);
        printf("%d %d %d %d\n", L1, L2, C1, C2);
}

int main()
{
        read();
        solve();
        write();
        return 0;
}