Cod sursa(job #1560563)

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

inline char bun(int l1, int l2, int c, int x, int m){
  int i, st, dr;
  st = dr = 0;
  for(i = 0; i < m; i++){
    s[i] = ma[l2][i];
    if(l1 != 0)
      s[i] -= ma[l1 - 1][i];
    s[i] -= 1LL * x * (l2 - l1 + 1);
  }
  for(i = 1; i < m; i++){
    s[i] += s[i - 1];
    if(i >= c - 1 && s[i] >= 0)
      return 1;
  }
  for(i = c; i < m; i++){
    if(i - dq[st] + 1 > m)
      st++;
    while(st < dr && s[i - c] < s[dq[dr - 1]])
      dr--;
    dq[dr] = i - c;
    dr++;
    if(st < dr && s[i] - s[dq[st]] >= 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, n2 = n / 2, l1, l2, cs;
  for(i = 0; i < n2; i++){
    l1 = (n2 + i - 1);
    l2 = i + l - 1;
    for(j = l2; j < n && j <= l1; j++){
      cs = 0;
      for(pas = (1 << 26); pas > 0; pas /= 2){
        if(bun(i, j, c, cs + pas, m))
          cs += pas;
      }
      if(rez < cs)
        rez = cs;
    }
  }
  FILE *out = fopen("balans.out", "w");
  fprintf(out, "%.3lf", 1.0 * rez / 1000);
  fclose(out);
  return 0;
}