Pagini recente » Cod sursa (job #646661) | Cod sursa (job #860669) | Cod sursa (job #3226223) | Cod sursa (job #1589471) | Cod sursa (job #1398113)
#include <fstream>
#include <deque>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream fin("balans.in");
ofstream fout("balans.out");
int N, M, R, C;
int sol;
int A[305][305];
long long sum[305][305], sumC[305];
deque<int> DQ;
bool solve(int cost)
{
for (int i = 1; i <= 2 * N; ++i)
for (int j = i + R - 1; j - i + 1 <= N && j <= 2 * N; ++j)
{
for (int k = 1; k <= 2 * M; ++k)
sumC[k] = sumC[k - 1] + sum[j][k] - sum[i - 1][k] - 1LL * cost * (j - i + 1);
DQ.clear();
for (int k = C; k <= 2 * M; ++k)
{
while (!DQ.empty() && sumC[k - C + 1] <= sumC[DQ.back() - 1])
DQ.pop_back();
DQ.push_back(k - C + 1);
while (DQ.front() < k - M + 1)
DQ.pop_front();
if (sumC[k] - sumC[DQ.front() - 1] >= 0)
return true;
}
}
return false;
}
void cb()
{
int lt = 0, rt = 100001 * 1000;
while (rt - lt >= 0)
{
int mid = (lt + rt) / 2;
if (solve(mid))
{
sol = mid;
lt = mid + 1;
}
else
rt = mid - 1;
}
}
int main()
{
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;
A[i + N][j] = A[i][j];
A[i][j + M] = A[i][j];
A[i + N][j + M] = A[i][j];
}
for (int i = 1; i <= 2 * N; ++i)
for (int j = 1; j <= 2 * M; ++j)
sum[i][j] = sum[i - 1][j] + 1LL * A[i][j];
cb();
fout << fixed << setprecision(3) << double(sol) / 1000.0 << '\n';
fin.close();
fout.close();
return 0;
}