Cod sursa(job #335579)

Utilizator nimicLeoveanu Mihaita Alexandru nimic Data 30 iulie 2009 15:16:22
Problema Balans Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <cstdio>
#include <cstring>

int n, m, r, c;
int a[333][333], sum[333], temp[333];
int best[160][160];

inline void compute(int sum[], int best[]){
     int tempSum = 0;
     for (int i=0; i<c; i++)
         tempSum += sum[i];
     for (int i=0; i<m; i++){
         int partSum = tempSum;
         for (int j=i+c-1; j<i+m; ){
             if (partSum > best[j-i])
                best[j-i] = partSum;
             partSum += sum[++j];
         }
         tempSum += sum[i+c] - sum[i];
     }
}

int main(){
    freopen("balans.in", "r", stdin);
    freopen("balans.out", "w", stdout);
    scanf("%d %d %d %d\n", &n, &m, &r, &c);
    for (int i=0; i<n; i++)
        for (int j=0; j<m; j++){
            scanf("%d", a[i]+j);
            a[i+n][j] = a[i][j+m] = a[i+n][j+m] = a[i][j];
        }
    for (int i=0; i<r; i++)
        for (int j=0; j<2*m; j++)
            temp[j] += a[i][j];
    for (int i=0; i<n; i++){
        memcpy(sum, temp, sizeof(sum[0])*2*m);
        
        for (int lin=i+r-1; lin<i+n; lin++){            
            compute(sum, best[lin-i]);
            
            for (int j=0; j<2*m; j++)
                sum[j] += a[lin+1][j];
        }
        
        for (int j=0; j<2*m; j++)
            temp[j] += a[i+r][j] - a[i][j];
    }
    
    double rez = 0.0;
    
    for (int i=r-1; i<n; i++)
        for (int j=c-1; j<m; j++){
            if ((double) best[i][j] / ((i+1)* (j+1)) > rez)
               rez = (double) best[i][j] / ((i+1)* (j+1));
        }           
    printf("%.3f\n", rez - 0.0004999);
    return 0;
}