Pagini recente » Cod sursa (job #1752430) | Cod sursa (job #678478) | Cod sursa (job #2375019) | Cod sursa (job #147146) | Cod sursa (job #384212)
Cod sursa(job #384212)
#include<stdio.h>
#define infile "balans.in"
#define outfile "balans.out"
#define nmax 313
#define vmax (100*1001)
int a[nmax][nmax]; //matricea initiala
int n,m; //numarul de linii respectiv coloane
int nn,mm; //dubmlul nr-ului de linii, respectiv coloane
int lin,col; //numarul minim de randuri respectiv coloane
double med; //media maxima
void read()
{
int i,j;
scanf("%d %d %d %d\n",&n,&m,&lin,&col);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d\n",&a[i][j]);
}
void init()
{
int i,j;
//punem matricea in dreapta, in jos, si in dreapta jos
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
a[i][m+j]=a[n+i][j]=a[n+i][m+j]=a[i][j];
//dublam numarul de linii si coloane
nn=n<<1;
mm=m<<1;
}
int verif(double med)
{
double b[nn+1][mm+1]; //b[i][j]=b[1][j]+a[i][j]-med
int i,j,k;
//construim b[]-ul
for(i=0;i<=mm;i++) b[0][i]=0;
for(i=1;i<=nn;i++)
for(b[i][0]=0,j=1;j<=mm;j++)
b[i][j]=b[i-1][j]+(double)a[i][j]-med;
//luam pe rand toate perechiile de linii
for(i=1;i<=nn;i++)
for(j=i+lin-1;j-i<n && j<=nn;j++)
{
double c[mm+1]; //suma tuturor coloanelor intre cele 2 linii
double d[mm+1]; //d[i]=suma maxima a unei secvente de lungime cel mult (m-c) ce se termina la poz i
int e[mm+1],st,dr; //deq
//construim c[]-ul
for(c[0]=0,k=1;k<=mm;k++)
c[k]=c[k-1]+b[j][k]-b[i-1][k];
//facem deque-ul
for(st=1,dr=0,k=1;k<=mm;k++)
{
while(st<=dr && c[e[dr]]>=c[k]) dr--;
e[++dr]=k;
while(st<=dr && k-e[st]>m-col) st++;
d[k]=c[k]-c[e[st]];
}
//verificam toate secventele
for(k=col;k<=(m<<1);k++)
if(c[k]-c[k-col]+d[k-col] >= 0)
return 1;
}
//daca am ajuns aici, inseamna ca media este prea mare
return 0;
}
void solve()
{
double mij,st=0,dr=vmax;
//cautam binar media
while(st<=dr)
{
mij=(st+dr)/2;
if(verif(mij)) med=mij,st=mij+0.00000000001;
else dr=mij-0.00000000001;
}
}
void write()
{
printf("%.3lf\n",med);
}
int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);
read();
init();
solve();
write();
fclose(stdin);
fclose(stdout);
return 0;
}