Cod sursa(job #2197529)
Utilizator | Data | 22 aprilie 2018 14:23:25 | |
---|---|---|---|
Problema | Zone | Scor | 90 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 4.92 kb |
#include <fstream>
#include <algorithm>
#include <cstring>
using namespace std;
ifstream fin("zone.in");
ofstream fout("zone.out");
const long long N=512;
long long n,v[N+5][N+5];
long long sir[100];
long long s[N+5][N+5];
long long ar1=(1<<30),ac1=ar1,ar2=ar1,ac2=ar1;
long long r1,r2,c1,c2;
bool viz[100];
long long sum(long long r1,long long c1,long long r2,long long c2)
{
return s[r2][c2]-s[r2][c1-1]-s[r1-1][c2]+s[r1-1][c1-1];
}
bool cmp(long long a,long long b,long long c,long long d)
{
if(a==ar1)
{
if(b==ac1)
{
if(c==ar2)
return a+b+c+d<ac1+ac2+ar1+ar2;
return c<ar2;
}
return b<ac1;
}
return a<ar1;
}
int main()
{
fin>>n;
for(long long i=1;i<=9;i++)
fin>>sir[i];
sort(sir+1,sir+9+1);
for(long long i=1;i<=n;i++)
{
long long cur=0;
for(long long j=1;j<=n;j++)
{
fin>>v[i][j];
cur+=v[i][j];
s[i][j]=s[i-1][j]+cur;
}
}
for(r1=1;r1<=n;r1++)
{
for(long long v1=1;v1<=9;v1++)
{
long long r=0,pas=(1<<10);
while(pas)
{
if(r+pas<=n && sum(1,1,r1,r+pas)<=sir[v1])
r+=pas;
pas/=2;
}
if(sum(1,1,r1,r+pas)==sir[v1])
{
viz[v1]=1;
c1=r;
for(long long v2=1;v2<=9;v2++)
if(viz[v2]==0)
{
r=c1+1;
pas=(1<<10);
while(pas)
{
if(r+pas<=n && sum(1,c1+1,r1,r+pas)<=sir[v2])
r+=pas;
pas/=2;
}
if(sum(1,c1+1,r1,r)==sir[v2])
{
viz[v2]=1;
c2=r;
for(long long v3=1;v3<=9;v3++)
if(viz[v3]==0)
{
r=r1+1;
pas=(1<<10);
while(pas)
{
if(r+pas<=n && sum(r1+1,1,r+pas,c1)<=sir[v3])
r+=pas;
pas/=2;
}
if(sum(r1+1,1,r,c1)==sir[v3])
{
r2=r;
viz[v3]=1;
long long val3,val5,val6,val7,val8,val9;
val3=sum(1,c2+1,r1,n);
val5=sum(r1+1,c1+1,r2,c2);
val6=sum(r1+1,c2+1,r2,n);
val7=sum(r2+1,1,n,c1);
val8=sum(r2+1,c1+1,n,c2);
val9=sum(r2+1,c2+1,n,n);
long long g3=0,g5=0,g6=0,g7=0,g8=0,g9=0;
for(long long i=1;i<=9;i++)if(viz[i]==0 && sir[i]==val3){viz[i]=1;g3=1;}
for(long long i=1;i<=9;i++)if(viz[i]==0 && sir[i]==val5){viz[i]=1;g5=1;}
for(long long i=1;i<=9;i++)if(viz[i]==0 && sir[i]==val6){viz[i]=1;g6=1;}
for(long long i=1;i<=9;i++)if(viz[i]==0 && sir[i]==val7){viz[i]=1;g7=1;}
for(long long i=1;i<=9;i++)if(viz[i]==0 && sir[i]==val8){viz[i]=1;g8=1;}
for(long long i=1;i<=9;i++)if(viz[i]==0 && sir[i]==val9){viz[i]=1;g9=1;}
if(g3*g5*g6*g7*g8*g9==1)
{
if(cmp(r1,c1,r2,c2)==1)
{
ar1=r1;
ar2=r2;
ac1=c1;
ac2=c2;
}
}
memset(viz,0,sizeof(viz));
viz[v1]=viz[v2]=1;
}
}
viz[v2]=0;
}
}
viz[v1]=0;
}
}
}
fout<<ar1<<" "<<ar2<<" "<<ac1<<" "<<ac2;
return 0;
}
/**
**/