Cod sursa(job #1560590)

Utilizator hrazvanHarsan Razvan hrazvan Data 2 ianuarie 2016 21:17:47
Problema Balans Scor 95
Compilator c Status done
Runda Arhiva de probleme Marime 1.81 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, m2 = (m / 2);
  st = dr = 0;
  s[0] = ma[l2][0] - 1LL * x * (l2 - l1 + 1);
  if(l1 != 0)
    s[0] -= ma[l1 - 1][0];
  if(c == 1 && s[0] > 0)
    return 1;
  for(i = 1; i < m; i++){
    s[i] = ma[l2][i] + s[i - 1] - 1LL * x * (l2 - l1 + 1);
    if(l1 != 0)
      s[i] -= ma[l1 - 1][i];
    if(i < m2 && i >= c - 1 && s[i] >= 0)
      return 1;
  }
  for(i = c; i < m; i++){
    if(i - dq[st] + 1 > m2)
      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, n2 = n / 2, l1, l2, cs, st, dr, k, mid;
  for(i = 0; i < n2; i++){
    l1 = (n2 + i - 1);
    l2 = i + l - 1;
    for(j = l2; j < n && j <= l1; j++){
      cs = 0;
      st = 0;  dr = (1 << 26);
      for(k = 0; k < 26 && st != dr; k++){
        mid = (st + dr) / 2;
        if(bun(i, j, c, mid, m))
          st = mid;
        else
          dr = mid - 1;
      }
      while(bun(i, j, c, st + 1, m))
        st++;
      if(rez < st)
        rez = st;
    }
  }
  FILE *out = fopen("balans.out", "w");
  fprintf(out, "%.3lf", 1.0 * rez / 1000);
  fclose(out);
  return 0;
}