Cod sursa(job #1500980)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 12 octombrie 2015 22:17:56
Problema Zone Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.38 kb
#include <cstdio>
#include <algorithm>

#define NMAX 517
#define LL long long

using namespace std;
int n, l1, l2, c1, c2, ans1, ans2, ans3, ans4;
LL v[NMAX], arr[NMAX][NMAX], tmp, val, val2, val3, cand[NMAX];

LL suma(int x1, int y1, int x2, int y2)
{
    return (arr[x2][y2] - arr[x2][y1-1] - arr[x1-1][y2] + arr[x1-1][y1-1]);
}
int cautbin(LL nr)
{
    int start = 1, step = (1<<10);
    LL sum;
    for(; step; step>>=1)
    {
        int index = start + step;
        if(index > n-2) continue;
        sum = suma(1, 1, l1, index);
        if(sum <= nr) start = index;
    }
    return start;
}
int cautbin2(LL nr)
{
    int start = c1 + 1, step = (1<<10);
    LL sum=0;
    for(; step; step>>=1)
    {
        int index = start + step;
        if(index > n-1) continue;
        sum = suma(1, c1+1, l1, index);
        if(sum <= nr) start = index;
    }
    return start;
}
int cautbin3(LL nr)
{
    int start = l1+1, step = (1<<10);
    LL sum=0;
    for(; step; step>>=1)
    {
        int index = start + step;
        if(index > n-1) continue;
        sum = suma(l1+1, 1, index, c1);
        if(sum <= nr) start = index;
    }
    return start;
}

int main()
{
    freopen("zone.in", "r", stdin);
    freopen("zone.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i<= 9; ++i) scanf("%lld", &v[i]);
    sort(v+1, v+10);
    for(int i = 1; i<= n; ++i)
    {
        for(int j = 1; j<= n; ++j)
        {
            scanf("%lld", &tmp);
            arr[i][j] = tmp + arr[i-1][j] + arr[i][j-1] - arr[i-1][j-1];
        }
    }
    for(int i = 1; i<= n-2; ++i)
    {
        l1 = i;
        for(int j = 1; j<= 9; ++j)
        {
            val = v[j];
            c1 = cautbin(val);
            if(suma(1, 1, l1, c1) != val) continue;
            for(int k = 1; k<= 9; ++k)
            {
                if(k == j) continue;
                val2 = v[k];
                c2 = cautbin2(val2);
                if(suma(1, c1+1, l1, c2) != val2) continue;
                for(int u = 1; u<= 9; ++u)
                {
                    if(u == j || u == k) continue;
                    val3 = v[u];
                    l2 = cautbin3(val3);
                    if(suma(l1+1, 1, l2, c1) != val3) continue;
                    //printf("candidat %d %d %d %d\n", l1, l2, c1, c2);
                    cand[1] = suma(l2+1, 1, n, c1);//7
                    cand[2] = suma(l2+1, c1+1, n, c2);//8
                    cand[3] = suma(l2+1, c2+1, n, n);//9
                    cand[4] = suma(l1+1, c2+1, l2, n);//6
                    cand[5] = suma(1, c2+1, l1, n);//3
                    cand[6] = suma(l1+1, c1+1, l2, c2);//5
                    cand[7] = suma(1, 1, l1, c1);//1
                    cand[8] = suma(1, c1+1, l1, c2);//2
                    cand[9] = suma(l1+1, 1, l2, c1);//4
                    sort(cand+1, cand+10);
                    bool f = 1;
                    for(int i = 1; i<= n; ++i)
                    {
                        if(v[i] != cand[i]) f = 0;
                    }
                    if(f)
                    {
                        ans1 = l1;
                        ans2 = l2;
                        ans3 = c1;
                        ans4 = c2;
                    }
                }
            }
        }
    }
    printf("%d %d %d %d\n", ans1, ans2, ans3, ans4);
    return 0;
}