Cod sursa(job #87277)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 26 septembrie 2007 21:50:16
Problema Zone Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <stdio.h>
#define NMAX ((1<<9)+10)

int A[NMAX][NMAX], N, M, V[10], S[NMAX][NMAX];
int C1[NMAX*NMAX], C2[NMAX*NMAX], S1[NMAX*NMAX], S2[NMAX*NMAX];
int C3[NMAX*NMAX], C4[NMAX*NMAX], S3[NMAX*NMAX], S4[NMAX*NMAX];
int X[NMAX], pred[NMAX], urm[NMAX];

int main()
{
        int i, j, k, t;
        int n1, n2, n3, n4, last;

        n1 = n2 = n3 = n4 = 0;
        
        freopen("zone.in", "r", stdin);
        scanf("%d %d", &N, &M);
        for (i = 0; i < 9; i++) scanf("%d", V+i);
        for (i = 1; i <= N; i++)
            for (j = 1; j <= M; j++)
            {
                scanf("%d", &A[i][j]);
                S[i][j] = S[i][j-1]+S[i-1][j]+A[i][j];
            }

        for (i = 1; i <= N; i++)
            for (j = 1; j <= M; j++)
                for (k = 0; k < 9; k++)
                {
                    if (S[i][j]==V[k]) C1[n1] = j, S1[n1++] = S[i][j];
                    if (S[N][M]-S[i-1][j-1]==V[k]) C4[n4] = j; S4[n4++] = S[N][M]-S[i][j];
                }

        for (i = N; i > 0; i--)
            for (j = 1; j <= M; j++)
                for (k = 0; k < 9; k++)
                {
                    if (S[N][j]-S[i-1][j-1]==V[k]) C2[n2] = j; C2[n2++] = S[N][j]-S[i-1][j-1];
                    if (S[i][M]-S[i-1][j-1]==V[k]) C3[n3] = j; C3[n3++] = S[i][M]-S[i-1][j-1];
                }

        for (i = 0; i < n1; i++) X[ C1[i] ] = 1;
        for (i = 0; i < n2; i++) X[ C2[i] ]++;

        last = 0;
        for (i = 0; i < NMAX; i++) {
            if (X[i]>1) urm[last] = i, last = i;
            X[i] = 0; }

        for (i = 0; i < n1; i++) X[ C3[i] ] = 1;
        for (i = 0; i < n2; i++) X[ C4[i] ]++;

        last = NMAX-1;
        for (i = NMAX-1; i >= 0; i--)
            if (X[i]>1) pred[last] = i, last = i;

        for (i = j = 0; i < N; i = urm[i])
        {
                for (;C1[j]<i;j++);
                for (;C1[j]==i;j++)
                {
                      t = 0;
                      for (k = pred[NMAX-1]; k > 0; k = pred[k])
                      {
                           for (;C3[t]<k;t++);
                           for (;C3[t]==k;t++)
                               X[t] = 0;
                      }
                }
        }
                
        return 0;
        
}