Cod sursa(job #1720663)

Utilizator Bodo171Bogdan Pop Bodo171 Data 22 iunie 2016 22:58:10
Problema Balans Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <iostream>
#include<fstream>
#include<string>
using namespace std;
const int en=155;
int d[2*en],a[en][en],num;
int i,j,n,m,k,newi,newj,N,M,u,p,r,c,i1,fix;
short ce;
long long el,minim[2*en],deq[2*en],s[2*en][2*en];
int pr,ul,em,x;
bool ok;
string st;
int main()
{
    ifstream f("balans.in");
    ofstream g("balans.out");
    f>>n>>m>>r>>c;
    f.get();
    for(i=1;i<=n;i++)
         {
             j=1;
             getline(f,st);ce=0;
             while(j<=m)
             {
                 if(st[ce]>='0'&&st[ce]<='9')
                 {
                     num=num*10+st[ce]-'0';
                 }
                 else
                 {a[i][j]=num*1000;j++;num=0;}
                 ce++;
             }
        }
        if(r==0) r++;
        if(c==0) c++;
    pr=0;ul=100000000;
    N=2*n;M=2*m;
    k=m-c;
    while(ul-pr>1)
    {
        x=(pr+ul)/2;
        ok=false;
    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;
    }
    for(i=r;i<=N&&ok==0;i++)
        {
            fix=max(0,i-n);
            for(i1=fix;i1<=i-r;i1++)
    {
      p=1;u=1;
      d[u]=0;deq[u]=0;el=0;
      for(j=1;j<=M&&ok==0;j++)
      {
          el+=s[i][j]-s[i1][j];
          if(i-d[p]>=k+1&&p<=u) p++;
          while(el<=deq[u]&&p<=u)
            u--;
          u++;
          deq[u]=el;
          d[u]=j;
          minim[j]=deq[p];
          if(k==0) minim[j]=el;
          if(j>=c) if(el-minim[j-c]>=0) ok=1;
      }
    }}
        if(ok) pr=x;
        else ul=x;
    }
    ul--;
    int part1=ul/1000;
    int part2=ul%1000;
    g<<part1;
    g<<".";
    if(part2<=10) g<<"00";
    else if(part2<=100) g<<"0";
    g<<part2;
    return 0;
}