Pagini recente » Cod sursa (job #1328103) | Cod sursa (job #2414504) | Cod sursa (job #2408896) | Cod sursa (job #1606555) | Cod sursa (job #938626)
Cod sursa(job #938626)
#include <fstream>
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 ();
int N2 = N << 1, M2 = M << 1;
for (int i = 1; i <= N2; i++)
for (int j = 1; j <= M2; j++)
mat[i][j] += mat[i - 1][j];
}
int Good (int a, int b, int K)
{
int p = M << 1;
for (int i = 1; i <= p; 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 <= p; 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 val = 0;
for (int step = 1 << 26; step; step >>= 1)
{
int found = 0;
for (int a = 1; a <= N; a++)
{
int alfa = a + N;
for (int b = a + R - 1; b < alfa; b++)
{
if (Good (a, b, step + val))
{
found = 1;
break;
}
}
if (found) break;
}
if (found) val += step;
}
return val;
}
void Scriere ()
{
ofstream fout ("balans.out");
int Ans = B_Search ();
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;
}