Pagini recente » Cod sursa (job #1684982) | Cod sursa (job #1055720) | Cod sursa (job #1624631) | Cod sursa (job #1029776) | Cod sursa (job #186412)
Cod sursa(job #186412)
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;
const int MAX_D = 151;
const long long MAX_AVG = 150000000LL;
const long long INF = 1LL << 50;
ifstream in("balans.in");
ofstream out("balans.out");
int M, N, R, C;
long long A[MAX_D << 1][MAX_D << 1];
long long S[MAX_D << 1], T[MAX_D << 1];
double balans = 0.;
void read() {
in >> M >> N >> R >> C;
for(int i = 1; i <= M; ++i)
for(int j = 1; j <= N; ++j) {
in >> A[i][j];
A[i][j] *= 1000;
A[i + M][j] = A[i][j + N] = A[i + M][j + N] = A[i][j];
}
for(int i = 1; i <= 2 * M; ++i)
for(int j = 1; j <= 2 * N; ++j)
A[i][j] += A[i - 1][j];
}
long long max_sum(long long X) {
for(int i = 1; i <= 2 * N; ++i)
T[i] = T[i - 1] + S[i] - X;
long long sum = -INF, t = INF;
for(int i = C; i <= 2 * N; ++i) {
t = min(t, T[i - C]);
sum = max(sum, T[i] - t);
}
return sum;
}
long long binary_search(const long long &lo, const long long &hi) {
if(lo == hi)
return lo;
if(max_sum((lo + hi) / 2) <= 0)
return binary_search(lo, (lo + hi) / 2);
else
return binary_search((lo + hi) / 2 + 1, hi);
}
void solve() {
if(!R) ++R;
if(!C) ++C;
for(; R <= M; ++R)
for(int i = 1; i <= M; ++i) {
for(int j = 1; j <= 2 * N; ++j)
S[j] = A[i + R - 1][j] - A[i - 1][j];
balans = max(balans, binary_search(1, MAX_AVG) / 1000. / R);
}
}
int main() {
read();
solve();
out << fixed << setprecision(3) << floor(balans * 1000.) / 1000. << "\n";
return 0;
}