Cod sursa(job #1837355)

Utilizator andrei-sasAndrei Sas-Miresan andrei-sas Data 29 decembrie 2016 15:51:43
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.17 kb
#include<bits/stdc++.h>
#define maxN 550
#define INF INT_MAX
using namespace std;
long long v[150];
int n,a[maxN][maxN],sol,st,dr,mid,l1,c1,l2,c2,j2,k1;
long long s[maxN][maxN];
long long s3,s4,s5,s6,s7,s8,s9;
int l1x=1000,l2x=1000,c1x=1000,c2x=1000;
vector<long long> el;
bool valid()
{
    sort(el.begin(),el.end());
    for(int i=0;i<9;i++)
    {
        if (v[i+1]!=el[i]) return 0;
    }
    return 1;
}
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("%d",&a[i][j]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        s[i][1]=s[i-1][1]+1LL*a[i][1];
        s[1][i]=s[1][i-1]+1LL*a[1][i];
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=2;j<=n;j++)
        {
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+1LL*a[i][j];
        }
    }
    for(int i=1;i<=9;i++)
    {
        //el.clear();
       // el.push_back(v[i]);
        for(int l1=1;l1<=(n-2);l1++)
        {
            st=1;
            dr=n-2;
            c1=0;
            while(st<=dr)
            {
                mid=(st+dr)>>1;
                if (s[l1][mid]==1LL*v[i])
                {
                    c1=mid;
                    st=dr+1;
                }
                    else
                if (s[l1][mid]<1LL*v[i]) st=mid+1;
                    else dr=mid-1;
            }
            if (c1)
            {
                for(int j=1;j<=9;j++)
                {
                    if (j!=i)
                    {
                        st=l1+1;
                        dr=n-1;
                        l2=0;
                        while(st<=dr)
                        {
                            mid=(st+dr)>>1;
                            if (s[mid][c1]==1LL*(v[i]+v[j]))
                            {
                            l2=mid;
                            st=dr+1;
                            }
                                else
                            if (s[mid][c1]<1LL*(v[i]+v[j])) st=mid+1;
                                else dr=mid-1;
                        }
                        if (l2)
                        {
                            for(int k=1;k<=9;k++)
                            {
                                if (k!=i && k!=j)
                                {
                                c2=0;
                                st=c1+1;
                                dr=n-1;
                                while(st<=dr)
                                {
                                    mid=(st+dr)>>1;
                                    if (s[l1][mid]==1LL*(v[i]+v[k]))
                                    {
                                        c2=mid;
                                        st=dr+1;
                                    }
                                        else
                                    if (s[l1][mid]<1LL*(v[i]+v[k])) st=mid+1;
                                        else dr=mid-1;
                                }
                                if (c2)
                                {
                                    el.clear();
                                    el.push_back(v[i]);
                                    el.push_back(v[j]);
                                    el.push_back(v[k]);
                                    s3=s[l1][n]-s[l1][c2];
                                    s5=s[l2][c2]-s[l2][c1]-v[k];
                                    s6=s[l2][n]-s[l2][c2]-s3;
                                    s7=s[n][c1]-s[l2][c1];
                                    s8=s[n][c2]-s[n][c1]-v[k]-s5;
                                    s9=s[n][n]-s[n][c2]-s6-s3;
                                    el.push_back(s3);
                                    el.push_back(s5);
                                    el.push_back(s6);
                                    el.push_back(s7);
                                    el.push_back(s8);
                                    el.push_back(s9);
                                    if (valid())
                                    {
                                     //   printf("%d %d %d %d\n",l1,l2,c1,c2);
                                        if (l1<l1x || (l1==l1x && c1<c1x) ||
                                            (l1==l1x && c1==c1x && l2<l2x) ||
                                            (l1==l1x && c1==c1x && l2==l2x && c2<c2x))
                                        {
                                            l1x=l1;
                                            l2x=l2;
                                            c1x=c1;
                                            c2x=c2;
                                        }
                                    }
                                }
                                }
                            }
                        }
                    }
                }
            }
        }

    }
    printf("%d %d %d %d\n",l1x,l2x,c1x,c2x);
    return 0;
}