Pagini recente » Cod sursa (job #291564) | Cod sursa (job #692602) | Cod sursa (job #1128410) | Cod sursa (job #921990) | Cod sursa (job #2333151)
#include<fstream>
#include<iomanip>
#include<queue>
using namespace std;
ifstream fi("balans.in");
ofstream fo("balans.out");
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()
{
fi>>n>>m>>r>>c;
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
{
fi>>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];
}
}
fo<<setprecision(3)<<fixed<<(1.0*rez/1000)<<"\n";
fi.close();
fo.close();
return 0;
}