Cod sursa(job #2072097)
Utilizator | Data | 21 noiembrie 2017 13:15:01 | |
---|---|---|---|
Problema | Zone | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 4.85 kb |
#include <fstream>
#include <algorithm>
#define ff first
#define s second
using namespace std;
ifstream fin ("zone.in");
ofstream fout("zone.out");
long long v[514][514],s[11];
long long f[11], i, j, n,c1,c2,l1,l2,k1,k2,k3,st,dr,mid,nr,m1,m2,m3,m4;
int verificare()
{
int i;
int ok=1;
for(i=1;i<=9;i++)
if(0LL+v[l1][n]-v[l1][c2]==s[i]&&f[i]==0)
f[i]=1;
for(i=1;i<=9;i++)
if(0LL+v[n][c1]-v[l2][c1]==s[i]&&f[i]==0)
f[i]=1;
for(i=1;i<=9;i++)
if(0LL+v[l2][c2]-v[l2][c1]-v[l1][c2]+v[l1][c1]==s[i]&&f[i]==0)
f[i]=1;
for(i=1;i<=9;i++)
if(0LL+v[l2][n]-v[l2][c2]-v[l1][n]+v[l1][c2]==s[i]&&f[i]==0)
f[i]=1;
for(i=1;i<=9;i++)
if(0LL+v[n][c2]-v[n][c1]-v[l2][c2]+v[l2][c1]==s[i]&&f[i]==0)
f[i]=1;
for(i=1;i<=9;i++)
if(0LL+v[n][n]-v[n][c2]-v[l2][n]+v[l2][c2]==s[i]&&f[i]==0)
f[i]=1;
for(i=1;i<=9;i++)
{
if(f[i]==0)
ok=0;
f[i]=0;
}
return ok;
}
int main ()
{
fin>>n;
for(i=1;i<=9;i++)
fin>>s[i];
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
fin>>v[i][j];
v[i][j]+=v[i][j-1]+v[i-1][j]-v[i-1][j-1];
}
m1=10000;
m2=10000;
m3=10000;
m4=10000;
for(k1=1;k1<=9;k1++)
for(k2=1;k2<=9;k2++)
if(k2!=k1)
for(k3=1;k3<=9;k3++)
if(k3!=k2&&k3!=k1)
for(l1=1;l1<n-1;l1++)
{
l2=-1;c1=-1;c2=-1;
st=1;
dr=n-2;
while(st<=dr)
{
mid=(st+dr)/2;
if(v[l1][mid]>=s[k1])
{
c1=mid;
dr=mid-1;
}
else
st=mid+1;
}
if(v[l1][c1]!=s[k1])
continue;
st=l1+1;
dr=n-1;
while(st<=dr)
{
mid=(st+dr)/2;
if(v[mid][c1]-v[l1][c1]>=s[k3])
{
l2=mid;
dr=mid-1;
}
else
st=mid+1;
}
if(v[l2][c1]-v[l1][c1]!=s[k3])
continue;
st=c1+1;
dr=n-1;
while(st<=dr)
{
mid=(st+dr)/2;
if(v[l1][mid]-v[l1][c1]>=s[k2])
{
c2=mid;
dr=mid-1;
}
else
st=mid+1;
}
if(v[l1][c2]-v[l1][c1]!=s[k2])
continue;
f[k1]=1;
f[k2]=1;
f[k3]=1;
if(verificare()==1)
{
nr++;
if(m1>l1)
m1=l1,m2=l2,m3=c1,m4=c2;
else
if(m1==l1)
{
if(m2>l2)
m2=l2,m3=c1,m4=c2;
else
if(m2==l2)
{
if(m3>c1)
m3=c1,m4=c2;
else
if(m3==c1)
{
if(m4>c2)
m4=c2;
}
}
}
}
}
fout<<m1<<" "<<m2<<" "<<m3<<" "<<m4;
return 0;
}