Cod sursa(job #1497680)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 7 octombrie 2015 09:28:07
Problema Balans Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <fstream>
#include <iomanip>
using namespace std;
ifstream f("balans.in");
ofstream g("balans.out");
int N,M,R,C;
long long Matrix[305][305],V[5];
long long Part[305][305];
const double eps = 0.001;
long long Left,Right=1000000000,mid,sol,Max;
void Read()
{
    f>>N>>M>>R>>C;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            f>>Matrix[i][j];
    for(int i=N+1;i<=2*N;i++)
        for(int j=1;j<=M;j++)
            Matrix[i][j]=Matrix[i-N][j];
    for(int i=1;i<=N;i++)
        for(int j=M+1;j<=2*M;j++)
            Matrix[i][j]=Matrix[i][j-M];
    N*=2;
    M*=2;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            Matrix[i][j]*=1000;
}
inline long long sum(int x1,int y1,int x2,int y2)
{
    return Part[x2][y2]-Part[x1-1][y2]-Part[x2][y1-1]+Part[x1-1][y1-1];
}
long long maxSum(long long X)
{
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            Part[i][j]=Part[i-1][j]+Part[i][j-1]-Part[i-1][j-1]+Matrix[i][j]-X;
    Max=-2000000005;
    for(int i=1;i<=N;i++)
        for(int j=i+R-1;j<=N;j++)
        {
            long long MMax,m=sum(i,1,j,C);
            MMax=m;
            for(int k=C+1;k<=M;k++)
            {
                m=max(m+sum(i,k,j,k),sum(i,k,j,k));
                MMax=max(MMax,m);
            }
            Max=max(Max,MMax);
        }
    return Max;
}

void binSearch()
{
    int count=30;
    while(Left<=Right && count>=0)
    {
        mid=(Left+Right)/2;
        if(maxSum(mid)>=0)
        {
            Left=mid+1;
            sol=mid;
            continue;
        }
        if(maxSum(mid)<0)
        {
            Right=mid-1;
            continue;
        }
    }
    g<<sol/1000<<".";
    int aux=sol%1000;
    while(aux!=0)
    {
        V[++V[0]]=aux%10;
        aux/=10;
    }
    while(V[0]<3)
        ++V[0];
    for(int i=V[0];i>=1;i--)
        g<<V[i];
    g<<"\n";
}
int main()
{
    Read();
    binSearch();
    return 0;
}