Cod sursa(job #1720575)

Utilizator Bodo171Bogdan Pop Bodo171 Data 22 iunie 2016 20:23:56
Problema Balans Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <iostream>
#include<fstream>
using namespace std;
const int en=155;
int minim[2*en],deq[en],d[en],a[en][en],s[2*en][2*en];
int i,j,n,m,k,newi,newj,N,M,p,ul,em,u,pr,r,c,i1,el;
int build(int 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(int 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]*=1000;}
    pr=0;ul=100000000;
    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/=1000;
    g<<rasp-0.001;
    return 0;
}