Uolevin kalansaalis

use std::fmt::{Debug, Display, Formatter};
use std::{cmp, io};

fn main() {
    let stdin = io::stdin();

    let (height, width, k) = {
        let mut input: String = String::new();
        stdin.read_line(&mut input).unwrap();
        let input = input.trim_end();

        let mut values = input.split_whitespace().map(|value| {
            value.parse::<usize>().unwrap()
        });

        (values.next().unwrap(), values.next().unwrap(), values.next().unwrap())
    };


    let (net, total_price_sum) = {
        // A vector of contents of the net. Indexed by net[coordinate.y][coordinate.x] where coordinate is a Coordinate.
        let mut net: Vec<Vec<i8>> = vec![vec![0; width]; height];

        // What the total sum would be without cutting any triangle
        let mut total_price_sum: i32 = 0;

        for _ in 0..k {
            let mut input: String = String::new();
            stdin.read_line(&mut input).unwrap();
            let input = input.trim_end();

            // Parse coordinate
            let mut values = input.split_whitespace();

            let coord = Coordinate {
                y: values.next().unwrap().parse::<usize>().unwrap() - 1,
                x: values.next().unwrap().parse::<usize>().unwrap() - 1
            };

            let content: i8 = match values.next().unwrap() {
                "H" | "h" => { 1 } // Hauki
                "K" | "k" => { -10 } // Katkarapu
                text => {
                    // Accept integer values for debugging
                    text.parse().unwrap_or_else(|_| panic!("Unknown content type! H or K?"))
                }
            };
            total_price_sum += content as i32;

            net[coord.y][coord.x] = content;
        }

        (net, total_price_sum)
    };

    // In the worst case, the net is full of 1s, so the smallest triangle would consist of one cell, the sum of which would be 1.
    let mut optimal_solution: i32 = 1;

    let optimal_solution_upwards: i32 = find_optimal_triangle(&net, height, width, false, optimal_solution);

    let optimal_solution_downwards: i32 = {
        let flipped_net: Vec<Vec<i8>> = net
            .iter()
            .rev()
            .map(|row|
                row
                    .iter()
                    .map(|v| *v)
                    .collect()
            )
            .collect();

        let is_shifted = height % 2 == 0; // Flipping the net causes the coordinate system to be shifted if the height is even.

        find_optimal_triangle(&flipped_net, height, width, is_shifted, optimal_solution)
    };

    optimal_solution = cmp::min(optimal_solution_upwards, optimal_solution_downwards);

    println!("{}", total_price_sum - optimal_solution);
}

/// Tries to find the smallest possible amount of profit possible (in other words, the smallest sum of the cells) within an upward-pointing triangle.
fn find_optimal_triangle(net: &Vec<Vec<i8>>, height: usize, width: usize, is_shifted: bool, mut optimal_solution: i32) -> i32 {
    /// Generates CellData for a cell that cannot continue any further
    fn ending_cell(content: i32) -> CellData {
        let v: Vec<i32> = vec![content];
        CellData {
            left_partial_table: v.clone(),
            complete_table: v,
        }
    }

    // Calculate bottom row manually
    let mut last_row = {
        let mut last_row: Vec<CellData> = Vec::with_capacity(width);
        let bottom_net_row = &net[height - 1];
        for i in 0..width {
            let content = bottom_net_row[i] as i32;
            if content < optimal_solution {
                optimal_solution = content;
            }
            last_row.push(ending_cell(content));
        }
        last_row
    };

    // Calculate for the rest of the rows.
    for y in (0..(height - 1)).rev() {
        let net_row = &net[y];
        let mut this_row = Vec::with_capacity(width);
        for x in 0..width {
            let coordinate = Coordinate { x, y };
            let content = *&net_row[x] as i32;
            let (left, right) = coordinate.get_coordinates_below(width, height, is_shifted);

            if left.is_none() || right.is_none() {
                // A triangle cannot continue further.
                if content < optimal_solution {
                    optimal_solution = content;
                }
                this_row.push(ending_cell(content));
            } else {
                // A triangle can continue further.

                // Get CellData for both cells below.
                let left = &last_row[left.unwrap().x];
                let right = &last_row[right.unwrap().x];

                let max_depth = cmp::min(left.left_partial_table.len(), right.complete_table.len()) + 1;

                let mut left_partial_table = Vec::with_capacity(max_depth);
                let mut complete_table = Vec::with_capacity(max_depth);

                for t in 0..max_depth {
                    let left_partial = if t > 0 { left.left_partial_table[t - 1] } else { 0 } + content;
                    left_partial_table.push(left_partial);

                    let complete = if t > 0 { right.complete_table[t - 1] } else { 0 } + left_partial;
                    complete_table.push(complete);

                    if complete < optimal_solution {
                        optimal_solution = complete;
                    }
                }

                this_row.push(CellData {
                    left_partial_table,
                    complete_table,
                });
            }
        }
        last_row = this_row;
    }

    optimal_solution
}

/// Represents a coordinate.
/// In this program the coordinate system is as follows:
/// - X axis is horizontally from left to right
/// - Y axis is vertically from TOP TO BOTTOM
/// - Coordinates start from 0
struct Coordinate {
    x: usize,
    y: usize
}

impl Debug for Coordinate {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        f.write_str(&*format!("({}, {}; x={}, y={})", &self.y + 1, &self.x + 1, &self.x, &self.y))
    }
}

impl Display for Coordinate {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        f.write_str(&*format!("({}, {})", &self.y + 1, &self.x + 1))
    }
}

impl Coordinate {
    /// Gets the coordinates for the cells below this coordinate. Returns as (left, right).
    /// The coordinate system is interpreted as follows:
    /// - If`!is_shifted`, the top left cell only has one cell below it to the right. Top right cell has cells below it on both sides.
    /// - If `is_shifted`, the top left cell also has a cell below it to the left, but the rightmost cell on the top row will not have a cell underneath it to the right.
    fn get_coordinates_below(&self, width: usize, height: usize, is_shifted: bool) -> (Option<Coordinate>, Option<Coordinate>) {
        assert!(self.x < width, "X is out of bounds");
        assert!(self.y < height, "Y is out of bounds");

        // If there is no row below
        if self.y >= height - 1 {
            return (None, None);
        }

        // Whether the leftmost cell of this row is located more to the left compared to adjacent rows.
        let starts_toward_left = self.y % 2 == if is_shifted { 1 } else { 0 };

        // Left
        let left: Option<usize> = match starts_toward_left {
            true => {
                if self.x > 0 {
                    Some(self.x - 1)
                } else {
                    None
                }
            }
            false => {
                Some(self.x)
            }
        };

        // Right
        let right: Option<usize> = match starts_toward_left {
            true => {
                Some(self.x)
            }
            false => {
                if self.x < width - 1 {
                    Some(self.x + 1)
                } else {
                    None
                }
            }
        };

        fn to_coordinate(x: Option<usize>, y: usize) -> Option<Coordinate> {
            x.and_then(|x| Some(Coordinate { x, y }))
        }
        return (to_coordinate(left, self.y + 1), to_coordinate(right, self.y + 1))
    }
}

struct CellData {
    /// If this was the tip of an upward-pointing triangle with the depth of t, the sum of its cells following its left edge would be `left_partial_table[t]`.
    left_partial_table: Vec<i32>,
    /// If this was the tip of an upward-pointing triangle with the depth of t, the sum of its cells would be `complete_table[t]`.
    complete_table: Vec<i32>
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 1, 2

Verdict: ACCEPTED

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: ACCEPTED

Test 14

Group: 1, 2

Verdict: ACCEPTED

Test 15

Group: 1, 2

Verdict: ACCEPTED

Test 16

Group: 2

Verdict: ACCEPTED

Test 17

Group: 2

Verdict: ACCEPTED

Test 18

Group: 2

Verdict: ACCEPTED

Test 19

Group: 2

Verdict: ACCEPTED

Test 20

Group: 2

Verdict: ACCEPTED

Test 21

Group: 2

Verdict: ACCEPTED

Test 22

Group: 2

Verdict: ACCEPTED

Test 23

Group: 2

Verdict: ACCEPTED

Test 24

Group: 2

Verdict: ACCEPTED