Cod sursa(job #2738942)

Utilizator MateiCatalinUrsache Matei MateiCatalin Data 6 aprilie 2021 16:28:19
Problema Zone Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.48 kb
#include <fstream>
#include <algorithm>

using namespace std;

long long a[513][513];
struct coordonate{int l,c;};
coordonate sus[270000],jos[270000];

int main()
{
    ifstream f("zone.in");
    ofstream g("zone.out");
    int n,z[10],zz[10],i,j,y,susn=0,josn=0,jc,l1,l2,c1,c2,s;
    long long sum=0;
    f>>n;
    for(i=1;i<=9;i++)
    {
        f>>z[i];
    }
    sort(z+1,z+10);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            f>>a[i][j];
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+a[i][j];
            for(y=1;y<=9;y++)
            {
                if(a[i][j]==z[y] && i<n && j<n)
                {
                    susn++;
                    sus[susn].l=i;
                    sus[susn].c=j;
                }
            }
        }
    }
    for(i=n-1;i>=1;i--)
    {
        for(j=n-1;j>=1;j--)
        {
            sum=a[n][n]-a[n][j-1]-a[i-1][n]+a[i-1][j-1];
            for(y=1;y<=9;y++)
            {
                if(sum==z[y])
                {
                    josn++;
                    jos[josn].l=i;
                    jos[josn].c=j;
                }
            }
        }
    }
    for(i=1;i<=susn;i++)
    {
        j=josn;
        while(jos[j].l<sus[i].l+1)
            j--;
        jc=j;
        for(j=jc;j>=1;j--)
        {
            if(jos[j].c>sus[i].c+1)
            {
                l1=sus[i].l;
                c1=sus[i].c;
                l2=jos[j].l;
                c2=jos[j].c;
                zz[1]=a[l1][c1];
                zz[9]=a[n][n]-a[n][c2-1]-a[l2-1][n]+a[l2-1][c2-1];
                zz[2]=a[l1][c2-1]-a[l1][c1];
                zz[3]=a[l1][n]-a[l1][c2-1];
                zz[4]=a[l2-1][c1]-a[l1][c1];
                zz[5]=a[l2-1][c2-1]-a[l2-1][c1]-a[l1][c2-1]+a[l1][c1];
                zz[6]=a[l2-1][n]-a[l2-1][c2-1]-a[l1][n]+a[l1][c2-1];
                zz[7]=a[n][c1]-a[l2-1][c1];
                zz[8]=a[n][c2-1]-a[n][c1]-a[l2-1][c2-1]+a[l2-1][c1];
                sort(zz+1,zz+10);
                s=1;
                for(y=1;y<=9;y++)
                   if(z[y]!=zz[y])
                        s=0;
                if(s==1)
                {
                    g<<l1<<" "<<l2-1<<" "<<c1<<" "<<c2-1;
                    j=0;
                    i=susn+1;
                }
            }
        }
    }
    f.close();
    g.close();
    return 0;
}