Cod sursa(job #2330700)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 28 ianuarie 2019 19:36:58
Problema Zone Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.96 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fi("zone.in");
ofstream fo("zone.out");
int n,i,j,k,l,l1,l2,c1,c2,ind;
long long S[520],A[520][520],Sum[520][520],Ans[520],suml;
bool b;
int main()
{
    fi>>n;
    for(i=1; i<=9; i++)
        fi>>S[i];
    sort(S+1,S+9+1);
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
        {
            fi>>A[i][j];
            Sum[i][j]=Sum[i][j-1]+Sum[i-1][j]-Sum[i-1][j-1]+A[i][j];
        }
    for(i=1; i<=9; i++)
        for(j=1; j<=9; j++)
        {
            if(j==i)
                continue;
            for(k=1; k<=9; k++)
            {
                if(k==i || k==j)
                    continue;
                suml=S[i]+S[j]+S[k];
                l1=0;
                for(ind=9; ind>=0; ind--)
                    if(l1+(1<<ind)<=n-2 && suml>=Sum[l1+(1<<ind)][n])
                        l1+=(1<<ind);
                if(Sum[l1][n]!=suml)
                    continue;
                c1=0;
                for(ind=9; ind>=0; ind--)
                    if(c1+(1<<ind)<=n-2 && S[i]>=Sum[l1][c1+(1<<ind)])
                        c1+=(1<<ind);
                if(Sum[l1][c1]!=S[i])
                    continue;
                c2=0;
                for(ind=9; ind>=0; ind--)
                    if(c2+(1<<ind)<=n-1 && S[i]+S[j]>=Sum[l1][c2+(1<<ind)])
                        c2+=(1<<ind);
                if(Sum[l1][c2]!=S[i]+S[j])
                    continue;
                for(l=1; l<=9; l++)
                {
                    if(l==i || l==j || l==k)
                        continue;
                    l2=0;
                    for(ind=9; ind>=0; ind--)
                        if(l2+(1<<ind)<=n-1 && S[i]+S[l]>=Sum[l2+(1<<ind)][c1])
                            l2+=(1<<ind);
                    if(S[i]+S[l]!=Sum[l2][c1])
                        continue;
                    Ans[1]=S[i];
                    Ans[2]=S[j];
                    Ans[3]=S[k];
                    Ans[4]=S[l];
                    Ans[5]=Sum[l2][c2]-Sum[l1][c2]-Sum[l2][c1]+Sum[l1][c1];
                    Ans[6]=Sum[l2][n]-Sum[l2][c2]-Sum[l1][n]+Sum[l1][c2];
                    Ans[7]=Sum[n][c1]-Sum[l2][c1];
                    Ans[8]=Sum[n][c2]-Sum[n][c1]-Sum[l2][c2]+Sum[l2][c1];
                    Ans[9]=Sum[n][n]-Sum[n][c2]-Sum[l2][n]+Sum[l2][c2];
                    sort(Ans+1,Ans+9+1);
                    b=1;
                    for(ind=1; ind<=9; ind++)
                        if(Ans[ind]!=S[ind])
                        {
                            b=0;
                            break;
                        }
                    if(b==1)
                    {
                        fo<<l1<<" "<<l2<<" "<<c1<<" "<<c2<<"\n";
                        fi.close();
                        fo.close();
                        return 0;
                    }
                }
            }
        }
    fi.close();
    fo.close();
    return 0;
}