Pagini recente » Cod sursa (job #2985676) | Cod sursa (job #414309) | Borderou de evaluare (job #1796314) | Borderou de evaluare (job #2010106) | Cod sursa (job #2641077)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <deque>
using namespace std;
ifstream in ("balans.in");
ofstream out("balans.out");
int n, m, lMin, cMin;
long long width, rezmax;
long long a[302][302], vec[302], vec2[302];
deque <short> q;
inline void scoate(short poz){
if(q.front()==poz) q.pop_front();
}
bool check(long long target){
q.clear();
for(int i=1; i<=2*m; i++)
vec2[i]=vec[i]-target*width+vec2[i-1];
if(vec2[cMin]>=0) return true;
for(int i=cMin+1; i<=2*m; i++){
while(!q.empty()&&vec2[q.back()]>=vec2[i-cMin])
q.pop_back();
q.push_back(i-cMin);
while(i-q.front()+1>m)
q.pop_front();
if(vec2[i]-vec2[q.front()]>=0) return true;
}
return false;
}
void twoPointer(short x1, short x2){
width=x2-x1+1;
for(int i=1; i<=2*m; i++)
vec[i]=a[x2][i]-a[x1-1][i];
long long st=0, dr=(1<<30), ans=0;
while(st<=dr){
long long mij=(st+dr)/2;
if(check(mij)){
ans=mij;
st=mij+1;
}
else
dr=mij-1;
}
rezmax=max(rezmax, ans);
}
int main()
{
in>>n>>m>>lMin>>cMin;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
{
in>>a[i][j];
a[i][j]*=1000;
a[n+i][j]=a[i][m+i]=a[n+i][m+j]=a[i][j];
}
for(int i=1; i<=2*n; i++)
for(int j=1; j<=2*m; j++)
a[i][j]+=a[i-1][j];
//twoPointer(3, 4);
for(int i=1; i<=2*n-lMin+1; i++)
for(int j=i+lMin-1; j-i+1<=n&&j<=2*n; j++)
twoPointer(i, j);
out<<fixed<<setprecision(3)<<(long double)rezmax/1000;
return 0;
}