Pagini recente » Cod sursa (job #1958358) | Cod sursa (job #1323822) | Cod sursa (job #1494462) | Cod sursa (job #2869363) | Cod sursa (job #1205137)
#include <algorithm>
#include <cstdio>
#include <deque>
using namespace std;
class FileInput {
public:
FileInput() {}
FileInput(const char *filename) {
file = fopen(filename, "r");
fread(buffer, BUFFER_SIZE, 1, file);
cursor = 0;
}
inline FileInput & operator >> (int &n) {
while(buffer[cursor] == ' ' || buffer[cursor] == '\n') {
advance();
}
n = 0;
while(isdigit(buffer[cursor])) {
n = n * 10 + buffer[cursor] - '0';
advance();
}
return *this;
}
private:
const static int BUFFER_SIZE = (1 << 20);
FILE* file;
char buffer[BUFFER_SIZE];
int cursor;
inline void advance() {
++ cursor;
if(cursor == BUFFER_SIZE) {
cursor = 0;
fread(buffer, BUFFER_SIZE, 1, file);
}
}
} cin("balans.in");
const int Nmax = 155;
const double EPS = 1e-8;
int Values[2 * Nmax][2 * Nmax], SumC[2 * Nmax][2 * Nmax];
double SumL[2 * Nmax];
int N, M, R, C;
bool Check(const double t)
{
for (int up = 0; up + R <= 2 * N; up++)
{
for (int down = up + R; down <= 2 * N && down - up <= N; down++)
{
for (int i = 1; i <= 2 * M; i++)
SumL[i] = SumL[i - 1] + SumC[down][i] - SumC[up][i] - t * (down - up);
deque<int> D;
for (int i = C; i <= 2 * M; i++)
{
while (!D.empty() && SumL[i - C] <= SumL[D.back()]) D.pop_back();
D.push_back(i - C);
while (!D.empty() && i - D.front() > M) D.pop_front();
if (!D.empty() && SumL[i] - SumL[D.front()] >= 0) return 1;
}
}
}
return 0;
}
int main()
{
freopen("balans.out", "w", stdout);
cin >> N >> M >> R >> C;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
cin >> Values[i][j];
for (int i = N + 1; i <= 2 * N; i++)
for (int j = 1; j <= M; j++)
Values[i][j] = Values[i - N][j];
for (int i = 1; i <= 2 * N; i++)
for (int j = M + 1; j <= 2 * M; j++)
Values[i][j] = Values[i][j - M];
for (int i = 1; i <= 2 * N; i++)
for (int j = 1; j <= 2 * M; j++)
SumC[i][j] = SumC[i - 1][j] + Values[i][j];
int Sol = 0;
for (int step = (1 << 26); step; step >>= 1)
{
if (Check((Sol | step) / 1000.0))
Sol |= step;
}
printf("%d.%d\n", Sol / 1000, Sol % 1000);
}