Pagini recente » Cod sursa (job #2144216) | Cod sursa (job #2526812) | Cod sursa (job #94281) | Cod sursa (job #1010542) | Cod sursa (job #1068511)
#include <iostream>
#include <fstream>
#include <deque>
#include <iomanip>
using namespace std;
const int Nmax = 151;
int N, M, R, C;
deque <int> deck;
double A[Nmax][Nmax];
double V[Nmax][Nmax];
double sum[Nmax][Nmax];
double sume_coloana[Nmax];
double sumCol[Nmax];
int valid( double cost )
{
double maxim = -10000000;
for ( int i = 1; i <= 2 * N; ++i )
{
for ( int j = 1; j <= 2 * M; ++j )
{
V[i][j] = A[i][j] - cost;
sum[i][j] = sum[i - 1][j] + V[i][j];
}
}
for ( int i = 1; i <= 2 * N; ++i )
{
for ( int j = i + R - 1; j - i < N && j <= 2 * N; ++j )
{
for ( int k = 1; k <= 2 * M; ++k )
{
sume_coloana[k] = sum[j][k] - sum[i - 1][k];
sumCol[k] = sumCol[k - 1] + sume_coloana[k];
}
/// intre C-M
deck.clear();
for ( int k = C; k <= 2 * M; ++k )
{
while ( deck.size() && sumCol[ deck.back() ] > sumCol[k - C] ) deck.pop_back();
while ( deck.size() && deck.front() < k - M ) deck.pop_front();
deck.push_back( k - C );
maxim = max( maxim, sumCol[k] - sumCol[ deck.front() ] );
}
}
}
return ( maxim >= 0 );
}
double cautare_binara()
{
double st = 0;
double dr = 15;
double sol = 0;
double m;
while ( dr - st > 0.0001 )
{
m = ( st + dr ) / 2.0;
if ( valid( m ) )
{
st = m;
sol = m;
}
else
{
dr = m;
}
}
return sol;
}
int main()
{
ifstream f("balans.in");
ofstream g("balans.out");
f >> N >> M >> R >> C;
for ( int i = 1; i <= N; ++i )
for ( int j = 1; j <= M; ++j )
{
f >> A[i][j];
A[i + N][j] = A[i][j + M] = A[i + N][j + M] = A[i][j];
}
g << fixed << setprecision( 3 );
g << cautare_binara();
return 0;
}