Pagini recente » Cod sursa (job #216146) | Cod sursa (job #564602) | Cod sursa (job #661013) | Cod sursa (job #2978622) | Cod sursa (job #2333166)
#include<stdio.h>
#include<queue>
using namespace std;
FILE *fi=fopen("balans.in","r");
FILE *fo=fopen("balans.out","w");
int n,m,i,j,k,rez,aux,r,c,A[305][305],Sum[305],S[305],Med[305],Min[305];
long long Aux[305];
deque<int> Q;
bool check(int x)
{
int i;
Q.clear();
for(i=1; i<=2*m; i++)
{
Aux[i]=Aux[i-1]+1LL*Med[i]-1LL*x;
if(i>=c && i<=m && Aux[i]>=0)
return 1;
if(!Q.empty() && i-Q.front()>(m-c))
Q.pop_front();
while(!Q.empty() && Aux[i]<=Aux[Q.back()])
Q.pop_back();
Q.push_back(i);
Min[i]=Q.front();
}
for(i=c+1; i<=2*m; i++)
if(Aux[i]-Aux[Min[i-c]]>=0)
return 1;
return 0;
}
int main()
{
fscanf(fi,"%d%d%d%d",&n,&m,&r,&c);
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
{
fscanf(fi,"%d",&A[i][j]);
A[i+n][j]=A[i][j];
A[i][j+m]=A[i][j];
A[i+n][j+m]=A[i][j];
}
for(i=1; i<=2*n; i++)
{
for(j=1; j<=2*m; j++)
{
Sum[j]+=A[i][j];
if(i>r)
Sum[j]-=A[i-r][j];
S[j]=Sum[j];
}
for(j=i-r+1; j>=max(1,j-n+1); j--)
{
for(k=1; k<=2*m; k++)
Med[k]=(1LL*S[k]*1000)/(i-j+1);
aux=0;
for(k=26; k>=0; k--)
if(check(aux+(1<<k)))
aux=aux+(1<<k);
rez=max(rez,aux);
for(k=1; k<=2*m; k++)
S[k]+=A[j-1][k];
}
}
fprintf(fo,"%.3f\n",1.0*rez/1000);
fclose(fi);
fclose(fo);
return 0;
}