Cod sursa(job #676971)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 9 februarie 2012 19:12:18
Problema Balans Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.74 kb
/*
#include <cstdio>

#define NMax 305
#define LL long long

using namespace std;

int N, M, R, C, D[NMax], A[NMax][NMax], AMax, AMin, Solution;
LL SumC[NMax][NMax];

template <class T>
T Max (T a, T b)
{
    if (a>b)
    {
        return a;
    }
    return b;
}

template <class T>
T Min (T a, T b)
{
    if (a<b)
    {
        return a;
    }
    return b;
}

inline LL MSS (LL Sum[])
{
    LL SMax=Sum[C];
    int F=1, B=0;
    D[1]=0;
    for (int i=C; i<=M+M; ++i)
    {
        while (F<=B and D[F]<i-M)
        {
            ++F;
        }
        while (F<=B and Sum[i-C]<=Sum[D[B]])
        {
            --B;
        }
        D[++B]=i-C;
        SMax=Max <LL> (SMax, Sum[i]-Sum[D[F]]);
        if (D[F]>M)
        {
            break;
        }
    }
    return SMax;
}

inline void BuildSum (LL Sum[], int L1, int L2, int S)
{
    Sum[0]=0;
    for (int i=1; i<=M+M; ++i)
    {
        Sum[i]=Sum[i-1]+SumC[L2][i]-SumC[L1-1][i]-(LL)(L2-L1+1)*(LL)S;
    }
}

inline bool FindMSM (int S)
{
    LL Sum[NMax];
    for (int L1=1; L1<=N; ++L1)
    {
        for (int L2=L1+R-1; L2<=L1+N-1; ++L2)
        {
             BuildSum (Sum, L1, L2, S);
             if (MSS (Sum)>=0)
             {
                 return true;
             }
        }
    }
    return false;
}

void Solve ()
{
    int L=AMin, R=AMax;
    while (L<=R)
    {
        int Mid=(L+R)/2;
        if (FindMSM (Mid))
        {
            Solution=Mid;
            L=Mid+1;
        }
        else
        {
            R=Mid-1;
        }
    }
}

void Read ()
{
    freopen ("balans.in", "r", stdin);
    scanf ("%d %d %d %d", &N, &M, &R, &C);
    for (int i=1; i<=N; ++i)
    {
        for (int j=1; j<=M; ++j)
        {
            scanf ("%d", &A[i][j]);
            A[i][j]*=1000;
            A[i+N][j]=A[i][j+M]=A[i+N][j+M]=A[i][j];
            AMax=Max <int> (AMax, A[i][j]);
            AMin=Min <int> (AMin, A[i][j]);
        }
    }
    for (int i=1; i<=N+N; ++i)
    {
        for (int j=1; j<=M+M; ++j)
        {
            SumC[i][j]=SumC[i-1][j]+A[i][j];
        }
    }
}

void Print ()
{
    freopen ("balans.out", "w", stdout);
    printf ("%.3lf\n", (Solution*1.0)/1000);
}

int main()
{
    Read ();
    Solve ();
    Print ();
    return 0;
}
*/

#include <stdio.h>
#define Nmax 155*2
#define CT 1000
#define LL long long
#define INF 2147000000

using namespace std;

int Deq[Nmax];
int a[Nmax][Nmax]; LL Sc[Nmax][Nmax];
LL Sum[Nmax];
int N,M,R,C;

inline LL Maxim(LL x,LL y){ return x>y ? x:y; }
inline LL Minim(LL x,LL y){ return x<y ? x:y; }

int bun(LL X){
	int i,i2,j,p,u; LL mx,sum_ac;

	for(i=1; i<=N; ++i)
		for(i2=i+R-1; i2<=i+N-1; ++i2){

			for(j=1;j<=2*M;++j) Sum[j]=Sum[j-1] + Sc[i2][j]-Sc[i-1][j] -X*(i2-i+1);

			p=1; u=0; mx=Sum[C];
			Deq[1]=1;
			for(j=C+1; j<=2*M; ++j){
				while( p<=u && Deq[p]+M-1 < j )
					p++;

				sum_ac=Sum[j]-Sum[j-C];
				while( u>=p && Sum[j]-Sum[Deq[u]-1] <= sum_ac )
					u--;
				Deq[++u]=j-C+1;

				mx=Maxim(mx,Sum[j]-Sum[Deq[p]-1]);
				if( Deq[p]>M ) break;
			}
			if( mx >= 0 )
				return 1;
		}
	return 0;
}

int main(){
	int i,j, Max=0,l,r,m,rez;
	freopen("balans.in","r",stdin);
	freopen("balans.out","w",stdout);
	scanf("%d%d%d%d",&N,&M,&R,&C);
	for(i=1;i<=N;++i)
		for(j=1;j<=M;++j){
			scanf("%d",&a[i][j]),a[i][j]*=CT;
			a[i+N][j]=a[i][j+M]=a[i+N][j+M]=a[i][j];

			Max=Maxim(a[i][j],Max);
		}
	for(i=1;i<=2*N;++i)
		for(j=1;j<=2*M;++j)
			Sc[i][j]=Sc[i-1][j]+(LL)(a[i][j]);

	for(l=0, r=Max; l<=r; ){
		m=l+(r-l)/2;
		if( bun(m) ){
			rez=m;
			l=m+1;
		}
		else r=m-1;
	}

	printf("%.3lf\n",(rez*1.0/CT));
	fclose(stdin); fclose(stdout);
	return 0;
}