Pagini recente » Cod sursa (job #2230507) | Cod sursa (job #938622)
Cod sursa(job #938622)
#include <fstream>
#include <iomanip>
using namespace std;
int N, M, R, C;
int mat[311][311];
char pars[1111];
long long v[311];
int Dq[1161];
void Citire ()
{
ifstream fin ("balans.in");
fin >> N >> M >> R >> C;
fin.getline (pars, 10);
for (int i = 1; i <= N; i++)
{
fin.getline (pars, 1101);
int a = 0, K = 0;
for (int j = 0; pars[j] != '\0'; j++)
{
if (pars[j] >= '0' && pars[j] <= '9') a = a * 10 + pars[j] - '0';
else
{
mat[i][++K] = a;
a = 0;
mat[i + N][K] = mat[i][K];
mat[i][K + M] = mat[i][K];
mat[i + N][K + M] = mat[i][K];
}
}
}
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] + 1LL * 1000 * (mat[b][i] - mat[a - 1][i]) - 1LL * (b - a + 1) * K;
int front = 0, marime = 1;
Dq[0] = 0;
if (v[C] >= 0) return 1;
for (int i = C + 1; i <= (M << 1); i++)
{
while (marime && i - Dq[front] > M) front++, marime--;
while (marime && v[Dq[front + marime - 1]] > v[i - C]) marime--;
Dq[front - 1 + ++marime] = i - C;
if (v[i] - v[Dq[front]] >= 0) return 1;
}
return 0;
}
int B_Search (int a, int b)
{
int val = 0;
for (int step = 1 << 26; 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;
}