# Cod sursa(job #2640903)

Utilizator Data 8 august 2020 23:50:32 Balans 25 cpp-64 done Arhiva de probleme 1.89 kb
``````#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 maxi, width, rezmax;
long long a[302][302], vec[302], vec2[302];
deque <short> q;
inline void baga(short poz){
while(!q.empty()&&vec2[q.back()]>=vec2[poz])
q.pop_back();
q.push_back(poz);
}
inline void scoate(short poz){
if(q.front()==poz) q.pop_front();
}
inline long long getSum(short x1, short y1, short x2, short y2){
return a[x2][y2]-a[x2][y1-1]-a[x1-1][y2]+a[x1-1][y1-1];
}
bool check(long long target){
q.clear();
long long sumMax=-1;
for(int i=1; i<=2*m; i++){
vec2[i]=vec[i]-target*width+vec2[i-1];
if(i-m>=0) scoate(i-m);
if(i-cMin>=0){
baga(i-cMin);
sumMax=max(sumMax, vec2[i]-vec2[q.front()]);
}
}
return sumMax>=0;
}
void twoPointer(short x1, short x2){
width=x2-x1+1; maxi=0;
for(int i=1; i<=2*m; i++)
vec[i]=getSum(x1, i, x2, i), maxi=max(maxi, vec[i]);
long long st=0, dr=maxi, 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]+a[i][j-1]-a[i-1][j-1];

//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;
}
``````