Cod sursa(job #1560525)

Utilizator hrazvanHarsan Razvan hrazvan Data 2 ianuarie 2016 20:00:52
Problema Balans Scor 85
Compilator c Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <stdio.h>
#define MAXN 300
#define EPS 0.0000001
#define INF 9000000000000000000.0
int ma[MAXN][MAXN], dq[MAXN];
long long s[MAXN], sum[MAXN];

inline double min2(double a, double b){
  return a < b ? a : b;
}

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; j < n && j <= l1; j++){
      for(k = 0; k < m; k++)
        sum[k] += ma[j][k];
      if(j >= l2){
        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, "%d", &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;
  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;
}