Cod sursa(job #1759814)
Utilizator | Data | 19 septembrie 2016 21:24:54 | |
---|---|---|---|
Problema | Zone | Scor | 80 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 5.13 kb |
#include<bits/stdc++.h>
#define maxN 550
#define INF INT_MAX
using namespace std;
int v[15],n,a[maxN][maxN],s[maxN][maxN],sol,st,dr,mid,l1,c1,l2,c2,j2,k1;
int s3,s4,s5,s6,s7,s8,s9;
int l1x=INF,l2x=INF,c1x=INF,c2x=INF;
vector<int> el;
bool valid(vector<int> a)
{
sort(a.begin(),a.end());
for(int i=0;i<a.size();i++)
{
if (v[i+1]!=a[i]) return 0;
}
return 1;
}
int main()
{
freopen("zone.in","r",stdin);
freopen("zone.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=9;i++)
{
scanf("%d",&v[i]);
}
sort(v+1,v+10);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
}
}
for(int i=1;i<=n;i++)
{
s[i][1]=s[i-1][1]+a[i][1];
s[1][i]=s[1][i-1]+a[1][i];
}
for(int i=2;i<=n;i++)
{
for(int j=2;j<=n;j++)
{
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
}
}
for(int i=1;i<=9;i++)
{
//el.clear();
// el.push_back(v[i]);
for(int l1=1;l1<=n ;l1++)
{
st=1;
dr=n-2;
c1=0;
while(st<=dr)
{
mid=(st+dr)>>1;
if (s[l1][mid]==v[i])
{
c1=mid;
st=dr+1;
}
else
if (s[l1][mid]<v[i]) st=mid+1;
else dr=mid-1;
}
if (c1)
{
for(int j=1;j<=9;j++)
{
if (j!=i)
{
st=l1+1;
dr=n-1;
l2=0;
while(st<=dr)
{
mid=(st+dr)>>1;
if (s[mid][c1]==(v[i]+v[j]))
{
l2=mid;
st=dr+1;
}
else
if (s[mid][c1]<(v[i]+v[j])) st=mid+1;
else dr=mid-1;
}
if (l2)
{
for(int k=1;k<=9;k++)
{
if (k!=i && k!=j)
{
c2=0;
st=1;
dr=n-1;
while(st<=dr)
{
mid=(st+dr)>>1;
if (s[l1][mid]==(v[i]+v[k]))
{
c2=mid;
st=dr+1;
}
else
if (s[l1][mid]<(v[i]+v[k])) st=mid+1;
else dr=mid-1;
}
if (c2)
{
el.clear();
el.push_back(v[i]);
el.push_back(v[j]);
el.push_back(v[k]);
s3=s[l1][n]-s[l1][c2];
s5=s[l2][c2]-s[l2][c1]-s[l1][c2]+s[l1][c1];
s6=s[l2][n]-s[l2][c2]-s3;
s7=s[n][c1]-s[l2][c1];
s8=s[n][c2]-s[n][c1]-v[k]-s5;
s9=s[n][n]-s[n][c2]-s[l2][n]+s[l2][c2];
el.push_back(s3);
el.push_back(s5);
el.push_back(s6);
el.push_back(s7);
el.push_back(s8);
el.push_back(s9);
if (valid(el))
{
// printf("%d %d %d %d\n",l1,l2,c1,c2);
if (l1<l1x || (l1==l1x && c1<c1x) ||
(l1==l1x && c1==c1x && l2<l2x) ||
(l1==l1x && c1==c1x && l2==l2x && c2<c2x))
{
l1x=l1;
l2x=l2;
c1x=c1;
c2x=c2;
}
}
}
}
}
}
}
}
}
}
}
printf("%d %d %d %d\n",l1x,l2x,c1x,c2x);
return 0;
}