Cod sursa(job #1723958)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 1 iulie 2016 21:55:30
Problema Balans Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include<cstdio>
#include<algorithm>
#define MAXN 160
using namespace std;
int a[2*MAXN][2*MAXN],n,m,r,c;
long long sum[2*MAXN][2*MAXN];
long long v[2*MAXN];
int Deque[MAXN];
bool Check(long long value){
    int i1,i2,j,left,right;
    long long best;
    for(i1=1;i1<=n;i1++)
        for(i2=i1+r-1;i2<=i1+n-1;i2++){
            for(j=1;j<=2*m;j++)
                v[j]=v[j-1]+sum[i2][j]-sum[i1-1][j]-value*(i2-i1+1);
            Deque[1]=1;
            left=1;
            right=0;
            best=v[c];
            for(j=c+1;j<=2*m&&Deque[left]<=m;j++){
                while(left<=right&&Deque[left]+m-1<j)
                    left++;
                while(left<=right&&v[Deque[right]-1]>=v[j-c])
                    right--;
                right++;
                Deque[right]=j-c+1;
                best=max(best,v[j]-v[Deque[left]-1]);
            }
            if(best>=0)
                return true;
        }
    return false;
}
int main(){
    freopen("balans.in","r",stdin);
    freopen("balans.out","w",stdout);
    int i,j,left=0,right=0,middle,answer;
    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]*=1000;
            a[i+n][j]=a[i][j+m]=a[i+n][j+m]=a[i][j];
            right=max(right,a[i][j]);
        }
    for(i=1;i<=2*n;i++)
        for(j=1;j<=2*m;j++)
            sum[i][j]=sum[i-1][j]+a[i][j];
    while(left<=right){
        middle=(left+right)/2;
        if(Check(middle)==true){
            answer=middle;
            left=middle+1;
        }
        else
            right=middle-1;
    }
    printf("%.3f",1.0*answer/1000);
    return 0;
}