Pagini recente » Cod sursa (job #2442082) | Borderou de evaluare (job #3182057) | Cod sursa (job #2689587) | Cod sursa (job #2508873) | Cod sursa (job #2917287)
/// Preset de infoarena
#include <fstream>
#include <deque>
#include <iomanip>
using namespace std;
ifstream fin("balans.in");
ofstream fout("balans.out");
#define int long long
const int maxN = 305;
int n, m, r, c;
int mat[maxN][maxN];
int aux[maxN][maxN], v[maxN];
bool check(int val)
{
for(int i = 1; i <= 2*n; i++)
for(int j = 1; j <= 2*m; j++)
aux[i][j] = aux[i - 1][j] + mat[i][j] - val;
for(int i1 = 1; i1 <= n; i1++)
{
for(int i2 = i1 + r - 1; i2 <= min(2 * n, i1 + n - 1); i2++)
{
deque <int> dq;
for(int j = 1; j <= 2 * m; j++)
{
v[j] = v[j - 1] + (aux[i2][j] - aux[i1 - 1][j]);
if(j >= c)
{
while(!dq.empty() && (dq.front() <= j - m))
dq.pop_front();
while(!dq.empty() && v[j - c] <= v[dq.back()])
dq.pop_back();
dq.push_back(j - c);
if(v[j] - v[dq.front()] >= 0)
return 1;
}
}
}
}
return 0;
}
signed main()
{
fin >> n >> m >> r >> c;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
fin >> mat[i][j];
mat[i][j] *= 1000;
mat[i + n][j] = mat[i][j];
mat[i][j + n] = mat[i][j];
mat[i + n][j + n] = mat[i][j];
}
}
int st = 0, dr = 1e8, ans = 0;
while(st <= dr)
{
int med = (st + dr) / 2;
if(check(med))
{
ans = med;
st = med + 1;
}
else
dr = med - 1;
}
double sol = 1.00 * ans / 1000;
fout << fixed << setprecision(3) << sol;
return 0;
}