Uolevin kalansaalis

warning: unused import: `max`
 --> input/code.rs:2:21
  |
2 | use std::cmp::{min, max};
  |                     ^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: associated function `empty_map_with_same_size` is never used
  --> input/code.rs:29:12
   |
29 |     pub fn empty_map_with_same_size(&self) -> Self {
   |            ^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

warning: 2 warnings emitted

use std::io::stdin;
use std::cmp::{min, max};

#[derive(Debug, Clone)]
struct PriceMap {
    width: usize,
    height: usize,
    map: Vec<Vec<i32>>,
}
impl PriceMap {
    pub fn new(width: usize, height: usize) -> Self {
        Self {
            width,
            height,
            map: vec![vec![0; width]; height]//array of rows to increase cache hit rate
        }
    }

    #[inline(always)]
    pub fn get(&self, x: usize, y: usize) -> i32 {
        self.map[y][x]
    }

    #[inline(always)]
    pub fn set(&mut self, x: usize, y: usize, price: i32) {
        self.map[y][x] = price;
    }

    pub fn empty_map_with_same_size(&self) -> Self {
        Self::new(self.width, self.height)
    }

    pub fn best_point_price(&self) -> i32 {
        *self.map
            .iter()
            .map(|row| row.iter())
            .flatten()
            .min()
            .unwrap()
    }

    pub fn flip(&mut self) {
        let max_y = self.height - 1;
        for y in 0..self.height {
            for x in 0..self.width {
                let a = self.get(x, y);
                let b = self.get(x, max_y - y);
                self.set(x, y, b);
                self.set(x, max_y - y, a);
            }
        }
    }
}

//only checks downwards pointing triangles
fn get_price_of_optimal_cut(price_map: &PriceMap) -> i32 {
    let mut triangle_price_map = price_map.clone();
    let mut line_price_map = price_map.clone();
    let mut best_price = price_map.best_point_price();

    let max_triangle_size = min(price_map.width, price_map.height);
    for triangle_size in 2..=max_triangle_size {
        let max_x = price_map.width - triangle_size;
        let max_y = price_map.height - triangle_size;

        for y in 0..=max_y {
            let triangle_x_offset = y % 2;

            for x in 0..=max_x {
                let point_price = price_map.get(x, y);
                let line_price = line_price_map.get(x + 1, y);
                let triangle_price = triangle_price_map.get(x + triangle_x_offset, y + 1);

                let new_line_price = line_price + point_price;
                let new_triangle_price = triangle_price + new_line_price;

                line_price_map.set(x, y, new_line_price);
                triangle_price_map.set(x, y, new_triangle_price);
                best_price = min(best_price, new_triangle_price);
            }
        }
    }

    best_price
}

fn main() {
    let mut input = stdin().lines();

    let line = input.next().unwrap().unwrap();
    let mut split = line.split_whitespace();
    let height: usize = split.next().unwrap().parse().unwrap();
    let width: usize = split.next().unwrap().parse().unwrap();
    let amount_of_fish: usize = split.next().unwrap().parse().unwrap();

    let mut price_map = PriceMap::new(width, height);
    let mut total_price: i32 = 0;
    for line_result in input.take(amount_of_fish) {
        let line = line_result.unwrap();
        let mut split = line.split_whitespace();
        let y: usize = split.next().unwrap().parse::<usize>().unwrap() - 1;
        let x: usize = split.next().unwrap().parse::<usize>().unwrap() - 1;
        let fish_type = split.next().unwrap();

        let price: i32 = match fish_type {
            "H" => 1,
            "K" => -10,
            _ => panic!("unknown fish type")
        };

        price_map.set(x, y, price);
        total_price += price;
    }

    let mut optimal_cut_price = get_price_of_optimal_cut(&price_map);
    price_map.flip();
    optimal_cut_price = min(optimal_cut_price, get_price_of_optimal_cut(&price_map));

    let best_price = total_price - optimal_cut_price;
    println!("{best_price}");
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 1, 2

Verdict: WRONG ANSWER

Test 3

Group: 1, 2

Verdict: ACCEPTED

Test 4

Group: 1, 2

Verdict: ACCEPTED

Test 5

Group: 1, 2

Verdict: ACCEPTED

Test 6

Group: 1, 2

Verdict: ACCEPTED

Test 7

Group: 1, 2

Verdict: ACCEPTED

Test 8

Group: 1, 2

Verdict: ACCEPTED

Test 9

Group: 1, 2

Verdict: ACCEPTED

Test 10

Group: 1, 2

Verdict: ACCEPTED

Test 11

Group: 1, 2

Verdict: ACCEPTED

Test 12

Group: 1, 2

Verdict: ACCEPTED

Test 13

Group: 1, 2

Verdict: WRONG ANSWER

Test 14

Group: 1, 2

Verdict: WRONG ANSWER

Test 15

Group: 1, 2

Verdict: ACCEPTED

Test 16

Group: 2

Verdict: WRONG ANSWER

Test 17

Group: 2

Verdict: WRONG ANSWER

Test 18

Group: 2

Verdict: ACCEPTED

Test 19

Group: 2

Verdict: ACCEPTED

Test 20

Group: 2

Verdict: WRONG ANSWER

Test 21

Group: 2

Verdict: ACCEPTED

Test 22

Group: 2

Verdict: ACCEPTED

Test 23

Group: 2

Verdict: ACCEPTED

Test 24

Group: 2

Verdict: ACCEPTED