Pagini recente » Cod sursa (job #2958826) | Cod sursa (job #715315) | Cod sursa (job #1885785) | Cod sursa (job #716196) | Cod sursa (job #384343)
Cod sursa(job #384343)
#include<stdio.h>
#define infile "balans.in"
#define outfile "balans.out"
#define nmax 313
#define zmax 1000
int a[nmax][nmax]; //matricea initiala
int b[nmax*nmax]; //toate elementele matricei
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
long long vmax; //suma celor mai mari lin*col elemente
long long vmin; //suma celor mai mici lin*col elemente
long long 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 unit(int st1, int dr1, int st2, int dr2)
{
int c[dr1-st1+2],st3,dr3;
for(st3=1,dr3=0;st1+dr3<=dr1;dr3++) c[dr3+1]=b[st1+dr3];
while(st3<=dr3 && st2<=dr2)
{
if(c[st3]<=b[st2]) b[st1++]=c[st3++];
else b[st1++]=b[st2++];
}
while(st3<=dr3) b[st1++]=c[st3++];
}
void msort(int st, int dr)
{
int mij=(st+dr)>>1;
if(st<mij) msort(st,mij);
if(mij+1<dr) msort(mij+1,dr);
unit(st,mij,mij+1,dr);
}
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;
//inmultim matricea cu 10^nr_zecimale
//pentru a nu mai lucra cu numere reale
//si salvam in vectorul b[] toate numerele
for(i=1;i<=nn;i++)
for(j=1;j<=mm;j++)
b[mm*(i-1)+j]=a[i][j]=a[i][j]*zmax;
//sortam numerele din vector
msort(1,nn*mm);
//aflam vmin
for(i=1;i<=lin*col;i++) vmin=vmin + (long long)b[i];
//aflam vmax
for(i=1;i<=lin*col;i++) vmax=vmax + (long long)b[nn*mm-i+1];
}
int verif(long long med)
{
long long b[nn+1][mm+1]; //b[i][j]=b[1][j]+a[i][j]-med
long long c[mm+1]; //suma tuturor coloanelor intre cele 2 linii
long long 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
int i,j,k;
int mcol=m-col;
int mmcol=mm-col;
//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]+(long long)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++)
{
//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(d[0]=0,st=1,dr=0,k=1;k<=mmcol;k++)
{
while(st<=dr && c[e[dr]]>=c[k]) dr--;
e[++dr]=k;
if(k-e[st]>mcol) st++;
d[k]=c[k]-c[e[st]];
}
//verificam secventele
for(k=col;k<=mm;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()
{
long long mij,st=vmin/(lin*col),dr=vmax/(lin*col);
//cautam binar media
while(st<=dr)
{
mij=(st+dr)/2;
if(verif(mij)) med=mij,st=mij+1;
else dr=mij-1;
}
}
void write()
{
printf("%.3lf\n",(double)med/zmax);
}
int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);
read();
init();
solve();
write();
fclose(stdin);
fclose(stdout);
return 0;
}