Task: | Uolevin kalansaalis |
Sender: | EmuBird |
Submission time: | 2023-11-02 18:45:03 +0200 |
Language: | Rust |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 37 |
#2 | ACCEPTED | 63 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.00 s | 1, 2 | details |
#2 | ACCEPTED | 0.00 s | 1, 2 | details |
#3 | ACCEPTED | 0.00 s | 1, 2 | details |
#4 | ACCEPTED | 0.00 s | 1, 2 | details |
#5 | ACCEPTED | 0.00 s | 1, 2 | details |
#6 | ACCEPTED | 0.00 s | 1, 2 | details |
#7 | ACCEPTED | 0.00 s | 1, 2 | details |
#8 | ACCEPTED | 0.00 s | 1, 2 | details |
#9 | ACCEPTED | 0.00 s | 1, 2 | details |
#10 | ACCEPTED | 0.00 s | 1, 2 | details |
#11 | ACCEPTED | 0.00 s | 1, 2 | details |
#12 | ACCEPTED | 0.00 s | 1, 2 | details |
#13 | ACCEPTED | 0.00 s | 1, 2 | details |
#14 | ACCEPTED | 0.00 s | 1, 2 | details |
#15 | ACCEPTED | 0.00 s | 1, 2 | details |
#16 | ACCEPTED | 0.53 s | 2 | details |
#17 | ACCEPTED | 0.53 s | 2 | details |
#18 | ACCEPTED | 0.55 s | 2 | details |
#19 | ACCEPTED | 0.52 s | 2 | details |
#20 | ACCEPTED | 0.53 s | 2 | details |
#21 | ACCEPTED | 0.52 s | 2 | details |
#22 | ACCEPTED | 0.52 s | 2 | details |
#23 | ACCEPTED | 0.52 s | 2 | details |
#24 | ACCEPTED | 0.53 s | 2 | details |
Code
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 trianglelet 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 coordinatelet 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 } // Katkaraputext => {// Accept integer values for debuggingtext.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 furtherfn ending_cell(content: i32) -> CellData {let v: Vec<i32> = vec![content];CellData {left_partial_table: v.clone(),complete_table: v,}}// Calculate bottom row manuallylet 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 0struct 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 belowif 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 };// Leftlet left: Option<usize> = match starts_toward_left {true => {if self.x > 0 {Some(self.x - 1)} else {None}}false => {Some(self.x)}};// Rightlet 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 details
Test 1
Group: 1, 2
Verdict: ACCEPTED
input |
---|
5 6 13 1 1 K 5 1 K 2 2 H 4 2 H ... |
correct output |
---|
-16 |
user output |
---|
-16 |
Test 2
Group: 1, 2
Verdict: ACCEPTED
input |
---|
5 6 7 1 5 K 4 6 K 2 4 H 2 5 H ... |
correct output |
---|
0 |
user output |
---|
0 |
Test 3
Group: 1, 2
Verdict: ACCEPTED
input |
---|
5 6 7 5 5 K 2 6 K 2 4 H 2 5 H ... |
correct output |
---|
0 |
user output |
---|
0 |
Test 4
Group: 1, 2
Verdict: ACCEPTED
input |
---|
10 10 51 3 3 H 6 3 H 9 5 H 5 10 H ... |
correct output |
---|
50 |
user output |
---|
50 |
Test 5
Group: 1, 2
Verdict: ACCEPTED
input |
---|
10 10 52 3 5 H 3 1 H 9 6 H 2 8 H ... |
correct output |
---|
40 |
user output |
---|
40 |
Test 6
Group: 1, 2
Verdict: ACCEPTED
input |
---|
10 10 60 6 10 H 2 8 H 5 8 H 8 10 H ... |
correct output |
---|
-15 |
user output |
---|
-15 |
Test 7
Group: 1, 2
Verdict: ACCEPTED
input |
---|
10 10 60 4 7 H 7 4 H 4 10 H 3 6 H ... |
correct output |
---|
60 |
user output |
---|
60 |
Test 8
Group: 1, 2
Verdict: ACCEPTED
input |
---|
10 10 40 9 9 H 5 10 H 5 6 H 4 9 H ... |
correct output |
---|
2 |
user output |
---|
2 |
Test 9
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1 1 0 |
correct output |
---|
0 |
user output |
---|
0 |
Test 10
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1 1 1 1 1 K |
correct output |
---|
0 |
user output |
---|
0 |
Test 11
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1 1 1 1 1 H |
correct output |
---|
0 |
user output |
---|
0 |
Test 12
Group: 1, 2
Verdict: ACCEPTED
input |
---|
10 5 32 10 3 H 4 4 H 3 3 H 5 4 H ... |
correct output |
---|
20 |
user output |
---|
20 |
Test 13
Group: 1, 2
Verdict: ACCEPTED
input |
---|
5 10 32 5 9 H 2 4 H 2 9 H 2 5 H ... |
correct output |
---|
28 |
user output |
---|
28 |
Test 14
Group: 1, 2
Verdict: ACCEPTED
input |
---|
10 10 100 2 9 H 5 4 H 5 9 K 6 1 K ... |
correct output |
---|
-439 |
user output |
---|
-439 |
Test 15
Group: 1, 2
Verdict: ACCEPTED
input |
---|
10 10 100 8 9 H 5 10 H 5 4 H 3 9 H ... |
correct output |
---|
88 |
user output |
---|
88 |
Test 16
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 125000 125 261 K 84 78 K 11 200 K 481 246 K ... |
correct output |
---|
-624270 |
user output |
---|
-624270 |
Test 17
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 125100 16 61 H 37 62 H 459 125 H 318 476 H ... |
correct output |
---|
124020 |
user output |
---|
124020 |
Test 18
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 249999 22 214 H 356 145 H 341 29 H 393 262 H ... |
correct output |
---|
249999 |
user output |
---|
249999 |
Test 19
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 32000 30 81 H 315 34 H 78 112 H 367 166 H ... |
correct output |
---|
10126 |
user output |
---|
10126 |
Test 20
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 126745 164 390 H 126 331 H 164 126 H 55 92 H ... |
correct output |
---|
-104692 |
user output |
---|
-104692 |
Test 21
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 71200 106 191 H 314 189 H 482 485 H 344 401 H ... |
correct output |
---|
-335853 |
user output |
---|
-335853 |
Test 22
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 67772 421 277 H 428 470 H 169 142 H 256 345 H ... |
correct output |
---|
-208567 |
user output |
---|
-208567 |
Test 23
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 27434 366 481 H 38 22 H 126 107 H 135 169 H ... |
correct output |
---|
-57100 |
user output |
---|
-57100 |
Test 24
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 93982 183 13 H 463 230 H 264 351 H 399 290 H ... |
correct output |
---|
-52800 |
user output |
---|
-52800 |