Cod sursa(job #594658)

Utilizator SpiderManSimoiu Robert SpiderMan Data 8 iunie 2011 18:40:52
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.59 kb
# include <cstdio>
# include <cstring>

typedef long long ll;
const char *FIN = "zone.in", *FOU = "zone.out" ;
const int MAX_N = 520, MAX_R = 9;

ll R[MAX_R], lin[MAX_N][MAX_N], col[MAX_N][MAX_N];
int N, l1 = MAX_N, c1, l2, c2;

inline ll calc (ll V[MAX_N][MAX_N], int l1, int c1, int l2, int c2) {
    return V[l2][c2] + V[l1][c1] - V[l2][c1] - V[l1][c2] ;
}

int binary (ll V[MAX_N], ll val) {
    int cnt, i;
    for (cnt = 1; cnt << 1 <= N; cnt <<= 1);
    for (i = 1; cnt; cnt >>= 1) {
        if (i + cnt <= N && V[i + cnt] <= val) {
            i += cnt ;
        }
    }
    return (V[i] == val ? i : -1) ;
}

bool check (int l1, int c1, int l2, int c2) {
    bool viz[MAX_R], see;
    const int l[] = {0, l1, l2, N},
              c[] = {0, c1, c2, N} ;
    memset (viz, 0, sizeof (viz));
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            ll aux = calc (lin, l[i], c[j], l[i + 1], c[j + 1]) ;
            see = 1;
            for (int k = 0; k < MAX_R && see; ++k) {
                if (viz[k] == 0 && R[k] == aux) {
                    viz[k] = 1, see = 0;
                }
            }
            if (see) return 0;
        }
    }
    return 1;
}

int main (void) {
    freopen (FIN, "r", stdin) ;

    scanf ("%d", &N) ;
    for (int i = 0; i < MAX_R; ++i)
        scanf ("%lld", R + i) ;
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            scanf ("%lld", lin[i] + j) ;
            lin[i][j] += lin[i - 1][j] + lin[i][j - 1] - lin[i - 1][j - 1];
            col[j][i] = lin[i][j] ;
        }
    }
    for (int i = 0; i < MAX_R; ++i) {
        for (int j = 1; j < N; ++j) {
            int auxc = binary (lin[j], R[i]);
            if (auxc == -1) continue ;
            for (int k = 0; k < MAX_R; ++k) {
                if (i == k) continue ;
                int auxl = binary (col[auxc], R[i] + R[k]);
                if (auxl == -1) continue ;
                for (int l = 0; l < MAX_R; ++l) {
                    if (i == l || k == l) continue ;
                    int aux = binary (lin[j], R[i] + R[l]);
                    if (aux == -1) continue ;
                    if (check (j, auxc, auxl, aux)) {
                        if (j < l1 || j == l1 && auxc < c1 || j == l1 && auxc == c1 && auxl < l2 || j == l1 && auxc == c1 && auxl == l2 && aux < c2) {
                            l1 = j, l2 = auxl, c1 = auxc, c2 = aux;
                        }
                    }
                }
            }
        }
    }
    fprintf (fopen (FOU, "w"), "%d %d %d %d", l1, l2, c1, c2);
}