Cod sursa(job #1720585)

Utilizator Bodo171Bogdan Pop Bodo171 Data 22 iunie 2016 20:32:11
Problema Balans Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <iostream>
#include<fstream>
#include<iomanip>
using namespace std;
const int en=155;
long long minim[2*en],deq[en],d[en],a[en][en],s[2*en][2*en],el;
int i,j,n,m,k,newi,newj,N,M,u,p,r,c,i1;
long long pr,ul,em;
void build(long long x)
{
    for(i=1;i<=N;i++)
        for(j=1;j<=M;j++)
    {
        newi=i,newj=j;
        if(newi>n) newi-=n;
        if(newj>m) newj-=m;
        s[i][j]=s[i-1][j]+a[newi][newj]-x;
    }
}
bool check(long long x)
{
    build(x);
    for(i=r;i<=N;i++)
        for(i1=max(0,i-n);i1<=i-r;i1++)
    {
      p=1;u=1;
      d[u]=0;deq[u]=0;el=0;
      for(j=1;j<=M;j++)
      {
          el+=s[i][j]-s[i1][j];
          if(i-d[p]>=k) p++;
          while(el<=deq[u]&&p<=u)
            u--;
          u++;
          deq[u]=el;
          d[u]=j;
          minim[j]=deq[u];
          if(j>=r) if(el-minim[j-c]>=0) return true;
      }
    }
    return false;
}
int main()
{
    ifstream f("balans.in");
    ofstream g("balans.out");
    f>>n>>m>>r>>c;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
         {f>>a[i][j];a[i][j]*=10000;}
    pr=0;ul=1000000000;
    N=2*n;M=2*m;
    k=m-c;
    while(ul-pr>1)
    {
        em=(pr+ul)/2;
        if(check(em)) pr=em;
        else ul=em;
    }
    double rasp=ul;
    rasp/=10000;
    g<<fixed<<setprecision(3)<<rasp;
    return 0;
}