Pagini recente » Cod sursa (job #2309202) | Cod sursa (job #2616626) | Cod sursa (job #2296457) | Cod sursa (job #804283) | Cod sursa (job #938615)
Cod sursa(job #938615)
#include <fstream>
#include <deque>
#include <iomanip>
using namespace std;
int N, M, R, C;
long long mat[311][311];
long long v[311];
deque <pair <long long, int> > Dq;
void Citire ()
{
ifstream fin ("balans.in");
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 + M] = mat[i][j];
mat[i + N][j + M] = mat[i][j];
}
}
fin.close ();
for (int i = 1; i <= (N << 1); i++)
for (int j = 1; j <= (M << 1); j++)
mat[i][j] += mat[i - 1][j];
}
int Good (int a, int b, int K)
{
for (int i = 1; i <= (M << 1); i++)
v[i] = v[i - 1] + mat[b][i] - mat[a - 1][i] - 1LL * (b - a + 1) * K;
Dq.clear ();
for (int i = C; i <= (M << 1); i++)
{
while (!Dq.empty () && i - Dq.front ().second > M) Dq.pop_front ();
while (!Dq.empty () && Dq.back ().first > v[i - C]) Dq.pop_back ();
Dq.push_back (make_pair (v[i - C], i - C));
if (v[i] - Dq.front ().first >= 0) return 1;
}
return 0;
}
int B_Search (int a, int b)
{
int val = 0;
for (int step = 1 << 30; step; step >>= 1)
if (Good (a, b, step + val)) val += step;
return val;
}
int Business ()
{
int Ans = -1;
for (int a = 1; a <= N; a++)
{
for (int b = a + R - 1; b < a + N; b++)
{
int local = B_Search (a, b);
if (local > Ans) Ans = local;
}
}
return Ans;
}
void Scriere ()
{
ofstream fout ("balans.out");
int Ans = Business ();
int zec = Ans % 1000;
fout << Ans / 1000 << ".";
if (zec < 10) fout << "00";
else if (zec < 100) fout << "0";
fout << zec;
fout.close ();
}
int main ()
{
Citire ();
Scriere ();
return 0;
}