Cod sursa(job #1560531)

Utilizator hrazvanHarsan Razvan hrazvan Data 2 ianuarie 2016 20:07:47
Problema Balans Scor 90
Compilator c Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <stdio.h>
#define MAXN 300
int dq[MAXN];
long long s[MAXN], sum[MAXN], ma[MAXN][MAXN];

inline char bun(int n, int m, int l, int c, int x){
  int i, j, k, st, dr, l1, l2, n2 = (n / 2), m2 = (m / 2);
  for(i = 0; i < (n >> 1); i++){
    for(j = 0; j < m; j++)
      sum[j] = 0;
    l1 = (n2 + i - 1);
    l2 = i + l - 1;
    for(j = i + l - 1; j < n && j <= l1; j++){
      for(k = 0; k < m; k++){
        sum[k] = ma[j][k];
        if(i != 0)
          sum[k] -= ma[i - 1][k];
      }
      st = dr = 0;
      s[0] = sum[0] - 1LL * (j - i + 1) * x;
      for(k = 1; k < m; k++){
        s[k] = s[k - 1] + sum[k] - 1LL * (j - i + 1) * x;
        if(st < dr && k - dq[st] + 1 > n / 2)
          st++;
        if(k >= c){
          while(st < dr && s[k - c] < s[dq[dr - 1]])
            dr--;
          dq[dr] = k - c;
          dr++;
        }
        if(st < dr && s[k] - s[dq[st]] >= 0)
          return 1;
      }
      for(k = c - 1; k < m2; k++)
        if(s[k] >= 0)
          return 1;
    }
  }
  return 0;
}

int main(){
  FILE *in = fopen("balans.in", "r");
  int n, m, l, c, i, j;
  fscanf(in, "%d%d%d%d", &n, &m, &l, &c);
  if(l == 0)
    l++;
  if(c == 0)
    c++;
  for(i = 0; i < n; i++){
    for(j = 0; j < m; j++){
      fscanf(in, "%lld", &ma[i][j]);
      ma[i][j] *= 1000;
      ma[i + n][j] = ma[i][j + m] = ma[i + n][j + m] = ma[i][j];
    }
  }
  n *= 2;  m *= 2;
  for(i = 1; i < n; i++)
    for(j = 0; j < m; j++)
      ma[i][j] += ma[i - 1][j];
  int rez = 0, pas;
  for(pas = (double)(1 << 26); pas > 0; pas /= 2){
    if(bun(n, m, l, c, rez + pas))
      rez += pas;
  }
  FILE *out = fopen("balans.out", "w");
  fprintf(out, "%.3lf", 1.0 * rez / 1000);
  fclose(out);
  return 0;
}