Cod sursa(job #3312990)

Utilizator Andrei1209Andrei Mircea Andrei1209 Data 1 octombrie 2025 17:25:53
Problema Balans Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.41 kb
#include <fstream>
#include <iomanip>
#include <deque>
using namespace std;
ifstream fin("balans.in");
ofstream fout("balans.out");
const int Nmax = 155 * 2;
double precizie =  1e-3;
int mat[Nmax][Nmax], sp_col[Nmax], n, m, r, c;
int i1, i2;
bool verif( double x )
{
    double sp[Nmax];
    int i;
    sp[0] = 0;
    for ( i = 1; i <= m; ++i )
        sp[i] = (double)sp_col[i] - x * (i2 - i1 + 1);
    for ( i = 1; i <= m; ++i )
    {
        sp[i] += sp[i - 1];
     //  if ( x == 11.5)
        //    fout << sp[i] << " ";
    }
    //if ( x == 11.5)
       // fout << endl;
    double sp_min = 0;
    int l = m / 2;
    deque <int> deq;
    for ( i = c; i <= m; ++i )
    {
        if (deq.front() < i - l )
            deq.pop_front();
        while ( deq.empty() == false && sp[deq.back()] > sp[i - c] )
            deq.pop_back();
        deq.push_back( i - c );
        sp_min  = sp[deq.front()];
        if ( sp[i] - sp_min >= 0 )
        {
           // if ( x == 11.5)
              //  fout << " secv buna are i = " << i << " si capat st = " << deq.front() + 1 << endl;
            return true;
        }
    }
    return false;
}
double calc()
{
    double st = 1, dr = 100000, mij, sol = 0;
    while ( dr - st > precizie )
    {
        mij = (st + dr) / 2;
        if ( verif(mij) )
        {
            sol = mij;
            st = mij;
        }
        else
            dr = mij;
    }
    return sol;
}
void reset()
{
    int i;
    for ( i = 1; i <= m; ++i )
        sp_col[i] = 0;
}
int main()
{
    int i, j;
    fin >> n >> m >> r >> c;
    for ( i = 1; i <= n; ++i )
        for ( j = 1; j <= m; ++j )
        {
            fin >> mat[i][j];
            mat[i + n][j] = mat[i + n][j + n] = mat[i][j + n] = mat[i][j];
        }

    n = 2 * n;
    m = 2 * m;
    double sol = 0;
    for ( i1 = 1; i1 <= n - r + 1; ++i1)
    {
        reset();
        for ( i = i1; i < i1 + r - 1; ++i )
            for ( j = 1; j <= m; ++j )
                sp_col[j] += mat[i][j];
        for ( i2 = i1 + r - 1; i2 <= n && i2 - i1 + 1 <= n / 2; ++i2 )
        {
            for ( j = 1; j <= m; ++j )
                sp_col[j] += mat[i2][j];
          //  if (i1 == 3 && i2 == 4)
             //   fout << "verif = " << verif(11.5) << endl;
            sol = max(sol, calc());
        }
    }
    fout << fixed << setprecision(3) << sol << '\n';
    return 0;
}