Cod sursa(job #2352542)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 23 februarie 2019 13:34:59
Problema Balans Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <bits/stdc++.h>
#define MAXN 164
#define MAXM 164

int a[2 * MAXN][2 * MAXM] ;
int pre[2 * MAXN][2 * MAXN] ;
std::deque<int>q ;
double crt[2 * MAXM] ;
int n, m, r, c ;

int verif(int stx, int len, double k) {
  int i  ;
  for (i = 1 ; i <= 2 * m ; ++ i)
    crt[i] = crt[i - 1] + pre[stx + len - 1][i] - pre[stx - 1][i] - (k * len) ;
  if (crt[c] >= 0)
    return 1 ;
  q.clear() ;
  for (i = c + 1 ; i <= 2 * m ; ++ i) {
    while (!q.empty() && crt[i - c] <= crt[q.back()])
      q.pop_back() ;
    q.push_back(i - c) ;
    while (q.size() > 1 && i - q.front() + 1 > m)
      q.pop_front() ;
    double scad = crt[q.front()] ;
    if (crt[i] - scad >= 0)
      return 1 ; }
  return 0 ; }
int main() {
  freopen("balans.in", "r", stdin) ;
  freopen("balans.out", "w", stdout) ;
  scanf("%d %d %d %d", &n, &m, &r, &c) ;
  int i, j, it  ;
  for (i = 1 ; i <= n ; ++ i)
    for (j = 1 ; j <= m ; ++ j) {
      scanf("%d", &a[i][j]) ;
      a[i][j + m] = a[i + n][j] = a[i + n][j + m] = a[i][j] ; }
  for (i = 1 ; i <= 2 * n ; ++ i)
    for (j = 1 ; j <= 2 * m ; ++ j)
      pre[i][j] = pre[i - 1][j] + a[i][j] ;
  int rez = 0 ;
  for (i = 1 ; i <= n ; ++ i)
    for (j = r ; j <= n ; ++ j) {
      int ls = rez, ld = (1 << 30), k ;
      if (!verif(i, j, ls / 1000.0))
        continue ;
      for (it = 1 ; it <= 30 && ls < ld ; ++ it) {
        k = (ls + ld) / 2 ;
        if (verif(i, j, k / 1000.0))
          ls = k ;
        else
          ld = k - 1 ; }
      for ( ; verif(i, j, ls / 1000.0) ; ++ ls) ;
      if (!verif(i, j, ls / 1000.0))
        --ls ;
      rez = std::max(rez, ls) ; }
  printf("%.3f", rez / 1000.0) ;
  return 0 ; }