Pagini recente » Cod sursa (job #1995569) | Cod sursa (job #1245748) | Cod sursa (job #2414869) | Cod sursa (job #516969) | Cod sursa (job #386949)
Cod sursa(job #386949)
#include <fstream>
#include <deque>
using namespace std;
const int MAX_N = 305;
const int INF = 0x3f3f3f3f;
ifstream fin ("balans.in");
int N, M, R, C, Max, Min, A[MAX_N][MAX_N];
long long S[MAX_N][MAX_N], T[MAX_N];
void citire()
{
fin >> N >> M >> R >> C;
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= M; ++j)
{
fin >> A[i][j];
A[i][j] *= 1000;
Max = max(Max, A[i][j]);
Min = min(Min, A[i][j]);
}
for(int i = 1; i <= N; ++i)
for(int j = M+1; j < 2*M; ++j)
A[i][j] = A[i][j-M];
for(int i = N+1; i < 2*N; ++i)
for(int j = 1; j < 2*M; ++j)
A[i][j] = A[i-N][j];
}
inline bool works(const int &x)
{
for(int i = 1; i < 2*N; ++i)
for(int j = 1; j < 2*M; ++j)
S[i][j] = S[i-1][j] + A[i][j] - x;
long long Sol = -1;
for(int i = 0; i < N; ++i)
for(int k = i+R; k <= i+N; ++k)
{
deque <int> Q;
for(int j = 1; j < 2*M; ++j)
T[j] = T[j-1] + S[k][j] - S[i][j];
for(int j = C; j < 2*M; ++j)
{
while(!Q.empty() && T[Q.back()] > T[j-C]) Q.pop_back();
while(!Q.empty() && Q.front() < j - M) Q.pop_front();
Q.push_back(j-C);
if(T[j] - T[Q.front()] > Sol)
Sol = T[j] - T[Q.front()];
}
}
return (Sol >= 0);
}
void solve()
{
int lg = 1, i = Min;
for(; lg <= Max; lg <<= 1);
for(; lg; lg >>= 1)
if(i + lg <= Max && works(i + lg))
i += lg;
freopen("balans.out","wt",stdout);
printf("%d.%03d\n",(i/1000), (i%1000));
}
int main()
{
citire();
solve();
}