Submission #1771617

---

Source Code Expand

fn main() {
  let n = get::val::<usize>();
  let dss = get::lists::<isize>(n);
  let q = get::val::<usize>();
  let qs = get::vals::<usize>(q);

  let mut g = Grid::new(dss, 0);
  g.accumulate();
  
  let mut maxv = vec![0; n*n+1];
  for x1 in 1 .. n+1 {
    for y1 in 1 .. n+1 {
      for x2 in x1 .. n+1 {
        for y2 in y1 .. n+1 {
          let area = (x2 - x1 + 1) * (y2 - y1 + 1);
          let val = g.sum(x1,y1,x2,y2);
          maxv[area] = std::cmp::max(maxv[area], val)
        }
      }
    }
  }
  
  for i in 1 .. maxv.len() {
    maxv[i] = std::cmp::max(maxv[i-1], maxv[i])
  }
  
  let ans = qs.into_iter().map(|a|maxv[a]).collect::<Vec<_>>();
  put::vec(&ans, "\n")
}

#[allow(dead_code)]
struct Grid {
  height: usize,
  width: usize,
  mat: Vec<Vec<isize>>
}

#[allow(dead_code)]
impl Grid {
  fn new(mat: Vec<Vec<isize>>, b: isize) -> Grid {
    let h = mat.len();
    let w = mat[0].len();
    let mut m = mat;
    
    for mut v in m.iter_mut() {
      v.insert(0, b);
      v.push(b)
    }
    let bs = (0..w+2).map(|_|b).collect::<Vec<_>>();
    m.insert(0, bs.clone());
    m.push(bs);
    
    Grid {height: h, width: w, mat: m}
  }

  fn height(&self) -> usize {
    self.height
  }

  fn width(&self) -> usize {
    self.width
  }

  fn get(&self, i: usize, j: usize) -> isize {
    self.mat[i][j]
  }

  fn put(&mut self, i: usize, j: usize, x: isize) {
    self.mat[i][j] = x
  }

  fn accumulate(&mut self) {
    for i in 1 .. self.height + 1 {
      for j in 1 .. self.width + 1 {
        self.mat[i][j] += self.mat[i][j-1]
      }
    }
    for i in 1 .. self.height + 1 {
      for j in 1 .. self.width + 1 {
        self.mat[i][j] += self.mat[i-1][j]
      }
    }
  }

  fn sum(&self, x1: usize, y1: usize, x2: usize, y2: usize) -> isize {
    self.mat[x2][y2] - self.mat[x1-1][y2] - self.mat[x2][y1-1] + self.mat[x1-1][y1-1]
  }

  fn print(&self) {
    for v in self.mat[1 .. self.height+1].iter() {
      let out = &v[1..self.width+1].iter().map(|e|format!("{:?}",e)).collect::<Vec<_>>().as_slice().join(" ");
      println!("{}", out);
    }
  }
}

#[allow(dead_code)]
mod get {
  use std::io::*;
  use std::str::*;

  pub fn val<T: FromStr>() -> T {
    let mut buf = String::new();
    let s = stdin();
    s.lock().read_line(&mut buf).ok();
    buf.trim_right().parse::<T>().ok().unwrap()
  }

  pub fn vals<T: FromStr>(n: usize) -> Vec<T> {
    let mut vec: Vec<T> = vec![];
    for _ in 0 .. n {
      vec.push(val());
    }
    vec
  }

  pub fn tuple<T1: FromStr, T2: FromStr>() -> (T1, T2) {
    let mut buf = String::new();
    let s = stdin();
    s.lock().read_line(&mut buf).ok();
    let mut it = buf.trim_right().split_whitespace();
    let x = it.next().unwrap().parse::<T1>().ok().unwrap();
    let y = it.next().unwrap().parse::<T2>().ok().unwrap();
    (x, y)
  }

  pub fn tuples<T1: FromStr, T2: FromStr>(n: usize) -> Vec<(T1, T2)> {
    let mut vec: Vec<(T1, T2)> = vec![];
    for _ in 0 .. n {
      vec.push(tuple());
    }
    vec
  }

  pub fn tuple3<T1: FromStr, T2: FromStr, T3: FromStr>() -> (T1, T2, T3) {
    let mut buf = String::new();
    let s = stdin();
    s.lock().read_line(&mut buf).ok();
    let mut it = buf.trim_right().split_whitespace();
    let x = it.next().unwrap().parse::<T1>().ok().unwrap();
    let y = it.next().unwrap().parse::<T2>().ok().unwrap();
    let z = it.next().unwrap().parse::<T3>().ok().unwrap();
    (x, y, z)
  }

  pub fn tuple3s<T1: FromStr, T2: FromStr, T3: FromStr>(n: usize) -> Vec<(T1, T2, T3)> {
    let mut vec: Vec<(T1, T2, T3)> = vec![];
    for _ in 0 .. n {
      vec.push(tuple3());
    }
    vec
  }

  pub fn list<T: FromStr>() -> Vec<T> {
    let mut buf = String::new();
    let s = stdin();
    s.lock().read_line(&mut buf).ok();
    buf.trim_right().split_whitespace().map(|t| t.parse::<T>().ok().unwrap()).collect()
  }

  pub fn lists<T: FromStr>(h: usize) -> Vec<Vec<T>> {
    let mut mat: Vec<Vec<T>> = vec![];
    for _ in 0 .. h {
      mat.push(list());
    }
    mat
  }

  pub fn chars() -> Vec<char> {
    let mut buf = String::new();
    let s = stdin();
    s.lock().read_line(&mut buf).ok();
    buf.trim_right().chars().collect()
  }
}

#[allow(dead_code)]
mod put {
  use std::string::*;

  pub fn vec<T: ToString>(vec: &Vec<T>, sep: &str) {
    let out = vec.iter().map(|e| e.to_string()).collect::<Vec<_>>().as_slice().join(sep);
    println!("{}", out);
  }

  pub fn mat<T: ToString>(mat: &Vec<Vec<T>>, sep: &str) {
    for v in mat {
      vec(v, sep);
    }
  }
}

Submission Info

Judge Result