Cod sursa(job #1738532)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 6 august 2016 22:18:08
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;

int taken;
i64 asp[550][550], sms[10];

inline i64 sum(int x0, int y0, int x1, int y1) {
    --x0;
    --y0;
    return asp[x1][y1] + asp[x0][y0] - asp[x1][y0] - asp[x0][y1];
}

bool push(int a, int b, int x, int y) {
    i64 val = sum(a, b, x, y);
    for(int i=1; i<=10-taken; ++i) {
        if(sms[i]==val) {
            swap(sms[i], sms[10-taken++]);

            return true;
        }
    }

    return false;
}

void pop(int a, int b, int x, int y) {
    i64 val = sum(a, b, x, y);
    for(int i=10; i>=10-taken; --i) {
        if(sms[i]==val) {
            swap(sms[i], sms[10-taken--]);

            return;
        }
    }
}

int main(void) {
    freopen("zone.in",  "r", stdin);
    freopen("zone.out", "w", stdout);
    int n, a, b, x, y;

    scanf("%d",&n);
    for(int i=1; i<=9; ++i)
        scanf("%lld",&sms[i]);
    for(int i=1; i<=n; ++i) {
    for(int j=1; j<=n; ++j) {
        scanf("%lld",&asp[i][j]);
        asp[i][j] -= asp[i-1][j-1];
        asp[i][j] += asp[i-1][j];
        asp[i][j] += asp[i][j-1];
    }}

    for(int a=1; a<n-1; ++a) {
    for(int b=1; b<n-1; ++b) {
        if(push(1, 1, a, b)) {
            for(int x=a+1; x<n; ++x) {
            if(push(a+1, 1, x, b)) {
                for(int y=b+1; y<n; ++y) {
                if(push(1, b+1, a, y)) {
                    if(push(a+1, b+1, x, y)) {
                        if(push(x+1, y+1, n, n)) {
                            if(push(a+1, y+1,  x, n)) {
                                if(push(x+1, b+1, n, y)) {
                                    if(push(1, y+1, a, n)) {
                                        if(push(x+1, 1, n, b)) {
                                            printf("%d %d %d %d\n",a,x,b,y);

                                            fclose(stdin);
                                            fclose(stdout);
                                            return 0;
                                        }
                                        pop(1, y+1, x, n);
                                    }
                                    pop(x+1, b+1, n, y);
                                }
                                pop(a+1, y+1,  x, n);
                            }
                            pop(x+1, y+1, n, n);
                        }
                        pop(a+1, b+1, x, y);
                    }
                    pop(1, b+1, a, y);
                }}
                pop(a+1, 1, x, b);
            }}
            pop(1, 1, a, b);
        }
    }}

    return 0;
}