Cod sursa(job #2738942)

Utilizator Data 6 aprilie 2021 16:28:19 Zone 80 cpp-64 done Arhiva de probleme 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;
}
``````