Cod sursa(job #1767205)
Utilizator | Data | 28 septembrie 2016 20:05:14 | |
---|---|---|---|
Problema | Zone | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.53 kb |
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin ("zone.in");
ofstream fout("zone.out");
int i, n, j, r, w, w1, a[515][515], sol1[515], sol2[515], ok, st, dr, mij, c[11], x, y, q;
int main()
{
fin>>n;
for(i=1;i<=9;i++)
fin>>c[i];
sort(c+1, c+9+1);
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
fin>>x;
a[i][j]=x+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
}
}
for(y=1;y<=9;y++){
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
if(a[i][j]==c[y]){
for(r=y+1;r<=9;r++){
ok=0;
st=j+1;
dr=n;
while(st<=dr){
mij=(st+dr)/2;
if(a[i][mij]-a[i][j]>c[r])
dr=mij-1;
else
if(a[i][mij]-a[i][j]<c[r])
st=mij+1;
else{
st=dr+1;
ok=1;
}
}
if(ok==1){
for(q=1;q<=9;q++){
if(c[q]==a[i][n]-a[i][mij]){
sol1[++w]=j;
sol1[++w]=mij;
}
}
}
ok=0;
st=i+1;
dr=n;
while(st<=dr){
mij=(st+dr)/2;
if(a[mij][j]-a[i][j]>c[r])
dr=mij-1;
else
if(a[mij][j]-a[i][j]<c[r])
st=mij+1;
else{
st=dr+1;
ok=1;
}
}
if(ok==1){
for(q=1;q<=9;q++){
if(c[q]==a[n][i]-a[mij][j]){
sol2[++w1]=i;
sol2[++w1]=mij;
}
}
}
}
}
}
}
}
return 0;
}