Pagini recente » Cod sursa (job #1995174) | Cod sursa (job #1464830) | Cod sursa (job #2398766) | Cod sursa (job #1738532) | Cod sursa (job #940426)
Cod sursa(job #940426)
#include <fstream>
#include <algorithm>
using namespace std;
FILE*f=fopen("zone.in", "r");
FILE*g=fopen("zone.out", "w");
int n, i, j, l1, l2, c1, c2, p, u, m, ok, s1, s2, s3, L1, L2, C1, C2, v[520][520];
long long a[520][520], s[10], b[10];
bool viz[10];
int cbc1(){
p=1;
u=n-2;
while(p<=u)
{
m=p+((u-p)>>1);
if(a[l1][m]==s[s1])
return m;
if(a[l1][m]<s[s1])
p=m+1;
else
u=m-1;
}
return 0;
}
int cbl2(){
p=l1+1;
u=n-1;
while(p<=u)
{
m=p+((u-p)>>1);
if(a[m][c1]-a[l1][c1]==s[s2])
return m;
if(a[m][c1]-a[l1][c1]<s[s2])
p=m+1;
else
u=m-1;
}
return 0;
}
int cbc2(){
p=c1+1;
u=n-1;
while(p<=u)
{
m=p+((u-p)>>1);
if(a[l1][m]-a[l1][c1]==s[s3])
return m;
if(a[l1][m]-a[l1][c1]<s[s3])
p=m+1;
else
u=m-1;
}
return 0;
}
void solutie(){
b[1]=s[s1];
b[2]=s[s3];
b[3]=a[l1][n]-a[l1][c2];
b[4]=s[s2];
b[5]=a[l2][c2]-a[l2][c1]-b[2];
b[6]=a[l2][n]-a[l2][c2]-b[3];
b[7]=a[n][c1]-a[l2][c1];
b[8]=a[n][c2]-a[l2][c2]-b[7];
b[9]=a[n][n]-a[l2][n]-b[7]-b[8];
sort(b+1, b+10);
bool ok=0;
for(i=1; i<10; i++)
if(s[i]!=b[i])
ok=1;
if(ok==0)
if(L1+L2+C1+C2>l1+l2+c1+c2)
{
L1=l1;
L2=l2;
C1=c1;
C2=c2;
}
}
int main(){
fscanf(f, "%d", &n);
for(i=1; i<10; i++)
fscanf(f, "%lld", &s[i]);
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
fscanf(f, "%d", &v[i][j]);
sort(s+1, s+10);
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
a[i][j]=v[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
L1=5000;
int N=n-1;
for(l1=1; l1<N; l1++)
for(s1=1; s1<10; s1++)
if( !viz[s1] )
{
c1=cbc1();
viz[s1]=1;
for(s2=1; s2<10; s2++)
if( !viz[s2] )
{
l2=cbl2();
viz[s2]=1;
for(s3=1; s3<10; s3++)
{
if( !viz[s3] )
{
c2=cbc2();
solutie();
}
}
viz[s2]=0;
}
viz[s1]=0;
}
fprintf(g, "%d %d %d %d", L1,L2, C1, C2);
return 0;
}