Cod sursa(job #1497653)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 7 octombrie 2015 03:06:06
Problema Zone Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.36 kb
#include <cstdio>
#include <algorithm>

#define LL long long
#define NMAX 517

using namespace std;

int n, l1, l2, c1, c2, f, tmp;
LL sum, v[11], sol[11], arr[NMAX][NMAX];

LL suma(int a1, int b1, int a2, int b2)
{
    return arr[a2][b2] + arr[a1][b1] - arr[a2][b1] - arr[a1][b2];
}
void cautbin()
{
    /*int start = 1, step = 1<<4;
    for(; step; step>>=1)
    {
        int index = start + step;
        if(index>9) continue;
        if(v[index] <= sum) start = index;
    }
    if(v[start] == sum) f = 1;*/
    for(int i = 1; i<= 9; ++i) if(v[i] == sum) f = 1;
}

int main()
{
    freopen("zone.in", "r", stdin);
    freopen("zone.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i<= 9; ++i) scanf("%d", &v[i]);
    sort(v+1, v+10);
    for(int i = 1; i<= n; ++i)
    {
        for(int j = 1; j<= n; ++j)
        {
            scanf("%d", &tmp);
            arr[i][j] = arr[i-1][j] + arr[i][j-1] - arr[i-1][j-1] + tmp;
        }
    }
    for(l1 = 1; l1 < n-1; ++l1)
    {
        for(c1 = 1; c1 < n-1; ++c1)
        {
            sum = suma(0, 0, l1, c1);
            f = 0;
            cautbin();
            if(!f) continue;
            for(l2 = l1+1; l2 < n-1; ++l2)
            {
                sum = suma(l1, 0, l2, c1);
                f = 0;
                cautbin();
                if(!f) continue;
                for(c2 = c1 + 1; c2 < n-1; ++c2)
                {
                    sum = suma(0, c1,l1, l2);
                    f = 0;
                    cautbin();
                    if(!f) continue;
                    sol[1] = suma(0, 0, l1, c1);
                    sol[2] = suma(0, c1, l1, c2);
                    sol[3] = suma(0, c2, l1, n);
                    sol[4] = suma(l1, 0, l2, c1);
                    sol[5] = suma(l1, c1, l2, c2);
                    sol[6] = suma(l1, c2, l2, n);
                    sol[7] = suma(l2, 0, n, c1);
                    sol[8] = suma(l2, c1, n, c2);
                    sol[9] = suma(l2, c2, n, n);
                    sort(sol+1, sol+10);
                    for(int i = 1; i<= 9; ++i) if(sol[i] != v[i]) f = 0;
                    if(f)
                    {
                        printf("%d %d %d %d\n", l1, l2, c1, c2);
                        return 0;
                    }
                }
            }
        }
    }
    return 0;
}