Cod sursa(job #1498758)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 9 octombrie 2015 01:05:13
Problema Balans Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <fstream>
#include <iomanip>
using namespace std;
ifstream f("balans.in");
ofstream g("balans.out");
int N,M,R,C;
int Matrix[305][305],V[5];
long long Part[305][305];
long long Array[305];
int Deque[305];
const double eps = 0.001;
int 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;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            Part[i][j]=Part[i-1][j]+Matrix[i][j];
}
inline long long sum(int x1,int y1,int x2,int y2,long long X)
{
    return Part[x2][y2]-Part[x1-1][y2]-Part[x2][y1-1]+Part[x1-1][y1-1]-X*(x2-x1+1)*(y2-y1+1);
}
int Sum(int x,int y,long long X)
{
    int Begin=1,End=0,point=1;
    long long Max=-10000000000000000;
    Deque[++End]=0;
    for(int i=1;i<C;i++)
        Array[i]=Array[i-1]+Part[y][i]-Part[x-1][i]-X*(y-x+1);
    for(int i=C;i<=M;i++)
    {
        Array[i]=Array[i-1]+Part[y][i]-Part[x-1][i]-X*(y-x+1);
        Max=max(Max,Array[i]-Array[Deque[Begin]]);
        if(Max>=0)
            return 1;
        while(Begin<=End && Array[point]<=Array[Deque[End]])
            --End;
        Deque[++End]=point;
        if(Deque[Begin]==i-M/2)
            ++Begin;
        ++point;
    }
    return -1;
}

int maxSum(long long X)
{

    Max=-10000000000000000;
    for(int i=1;i<=N/2;i++)
        for(int j=i+R-1;j<=N && j-i+1<=N/2;j++)
        {
            Max=max(Max,Sum(i,j,X));
            if(Max>=0)
                return 1;
        }
    return -1;
}

void binSearch()
{
    int count=30;
    while(Left<=Right && count>=0)
    {
        mid=(Left+Right)/2;
        if(maxSum(mid)>=0)
        {
            Left=mid+1;
            sol=mid;
            continue;
        }
        Right=mid-1;
    }
    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;
}