Cod sursa(job #479069)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 22 august 2010 15:46:18
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.14 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

#define ll long long

int a[550][550],n;
ll s[550][550],z[13],v[13];

inline ll sp(int px1,int py1,int px2,int py2)
{
    return (s[px2][py2]-s[px1-1][py2]-s[px2][py1-1]+s[px1-1][py1-1]);
}

int verifica(int l1,int l2,int c1,int c2)
{
    int i;
    z[1]=sp(1,1,l1,c1);
    z[2]=sp(1,c1+1,l1,c2);
    z[3]=sp(1,c2+1,l1,n);
    z[4]=sp(l1+1,1,l2,c1);
    z[5]=sp(l1+1,c1+1,l2,c2);
    z[6]=sp(l1+1,c2+1,l2,n);
    z[7]=sp(l2+1,1,n,c1);
    z[8]=sp(l2+1,c1+1,n,c2);
    z[9]=sp(l2+1,c2+1,n,n);
    sort(z+1,z+10);
    for(i=1;i<=9;i++)
        if(z[i]!=v[i])
            return 0;
    return 1;
}

int main ()
{
    int i,j,st,dr,c1,l1;
    int l2,z1,z2,z3,mij;
    ll sum;
    freopen("zone.in","r",stdin);
    freopen("zone.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=9;i++)
        scanf("%lld",&v[i]);
    sort(v+1,v+10);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            scanf("%d",&a[i][j]);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
    for(l1=1;l1<n-1;l1++)
        for(z1=1;z1<=9;z1++)
        {
            st=1;dr=n;
            while(st<=dr)
            {
                mij=(st+dr)/2;
                sum=sp(1,1,l1,mij);
                if(sum<v[z1])
                    st=mij+1;
                else
                    if(sum>v[z1])
                        dr=mij-1;
                    else
                        break;
            }
            if(st>dr)
                continue;
            c1=mij;
            for(z3=1;z3<=9;z3++)
            {
                if(z3==z1)
                    continue;
                st=l1+1;dr=n;
                while(st<=dr)
                {
                    mij=(st+dr)/2;
                    sum=sp(l1+1,1,mij,c1);
                    if(sum<v[z3])
                        st=mij+1;
                    else
                        if(sum>v[z3])
                            dr=mij-1;
                        else
                            break;
                }
                if(st>dr)
                    continue;
                l2=mij;
                for(z2=1;z2<=9;z2++)
                {
                    if(z2==z1 || z2==z3)
                        continue;
                    st=c1+1;dr=n;
                    while(st<=dr)
                    {
                        mij=(st+dr)/2;
                        sum=sp(1,c1+1,l1,mij);
                        if(sum<v[z2])
                            st=mij+1;
                        else
                            if(sum>v[z2])
                                dr=mij-1;
                            else
                                break;
                    }
                    if(st>dr)
                        continue;
                    if(verifica(l1,l2,c1,mij))
                    {
                        printf("%d %d %d %d\n",l1,l2,c1,mij);
                        return 0;
                    }
                }//for z2
            }//for z3
        }// for z1
    return 0;
}