Cod sursa(job #1757259)
Utilizator | Data | 14 septembrie 2016 19:19:38 | |
---|---|---|---|
Problema | Zone | Scor | 90 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 3.48 kb |
#include <algorithm>
#include <fstream>
using namespace std;
ifstream fin("zone.in");
ofstream fout("zone.out");
typedef long long i64;
const int nmax= 512;
bool u[9];
i64 v[9], v2[9], s[nmax+1][nmax+1];
i64 sum( i64 i1, i64 j1, i64 i2, i64 j2 ) {
return (i64)s[i2][j2]-s[i2][j1-1]-s[i1-1][j2]+s[i1-1][j1-1];
}
int main( ) {
i64 n, n2;
fin>>n;
for ( n2= 1; n2*2<=n; n2*= 2 ) ;
for ( i64 i= 0; i<9; ++i ) {
fin>>v[i];
}
sort( v, v+9 );
for ( i64 i= 1; i<=n; ++i ) {
for ( i64 j= 1; j<=n; ++j ) {
fin>>s[i][j];
s[i][j]= s[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}
}
i64 l1= 0, l2= 0, c1= 0, c2= 0;
for ( i64 i1= 1; i1<=n-2; ++i1 ) {
for ( i64 j1= 0; j1<9; ++j1 ) {
i64 x1= 0;
for ( i64 step= n2; step>0; step/= 2 ) {
if ( x1+step<=n-2 && s[i1][x1+step]<=v[j1] ) {
x1+= step;
}
}
if ( s[i1][x1]==v[j1] ) {
u[j1]= 1;
for ( i64 j2= 0; j2<9; ++j2 ) {
if ( u[j2]==0 ) {
i64 x2= 0;
for ( i64 step= n2; step>0; step/= 2 ) {
if ( x2+step<=n-1 && s[i1][x2+step]-v[j1]<=v[j2] ) {
x2+= step;
}
}
if ( s[i1][x2]-v[j1]==v[j2] ) {
u[j2]= 1;
for ( i64 j3= 0; j3<9; ++j3 ) {
if ( u[j3]==0 ) {
u[j3]= 1;
i64 i2= 0;
for ( i64 step= n2; step>0; step/= 2 ) {
if ( i2+step<=n-1 && s[i2+step][x1]-s[i1][x1]<=v[j3] ) {
i2+= step;
}
}
v2[0]= sum(1, 1, i1, x1);
v2[1]= sum(1, x1+1, i1, x2);
v2[2]= sum(1, x2+1, i1, n);
v2[3]= sum(i1+1, 1, i2, x1);
v2[4]= sum(i1+1, x1+1, i2, x2);
v2[5]= sum(i1+1, x2+1, i2, n);
v2[6]= sum(i2+1, 1, n, x1);
v2[7]= sum(i2+1, x1+1, n, x2);
v2[8]= sum(i2+1, x2+1, n, n);
sort( v2, v2+9 );
i64 aux= 0;
for ( i64 i= 0; i<9; ++i ) {
if ( v[i]==v2[i] ) {
++aux;
}
}
if ( aux==9 ) {
l1= i1, l2= i2, c1= x1, c2= x2;
}
u[j3]= 0;
}
}
u[j2]= 0;
}
}
}
u[j1]= 0;
}
}
}
fout<<l1<<" "<<l2<<" "<<c1<<" "<<c2<<"\n";
return 0;
}