CSES - Datatähti 2024 alku - Results
Submission details
Task:Uolevin kalansaalis
Sender:Bliz
Submission time:2023-11-01 15:20:24 +0200
Language:Rust
Status:READY
Result:37
Feedback
groupverdictscore
#1ACCEPTED37
#20
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 2details
#2ACCEPTED0.00 s1, 2details
#3ACCEPTED0.00 s1, 2details
#4ACCEPTED0.00 s1, 2details
#5ACCEPTED0.00 s1, 2details
#6ACCEPTED0.00 s1, 2details
#7ACCEPTED0.00 s1, 2details
#8ACCEPTED0.00 s1, 2details
#9ACCEPTED0.00 s1, 2details
#10ACCEPTED0.00 s1, 2details
#11ACCEPTED0.00 s1, 2details
#12ACCEPTED0.00 s1, 2details
#13ACCEPTED0.00 s1, 2details
#14ACCEPTED0.00 s1, 2details
#15ACCEPTED0.00 s1, 2details
#16--2details
#17--2details
#18--2details
#19--2details
#20--2details
#21--2details
#22--2details
#23--2details
#24--2details

Code

use std::{cmp, io};
type Net = Vec<Vec<i32>>;
#[derive(Clone, Copy)]
enum TriangleDir {
Up,
Down,
}
fn main() {
let (n, m, k) = read_n_m_k();
let mut net: Net = vec![vec![0; m]; n];
read_net_contents(k, &mut net);
println!("{}", find_max_profit(&mut net, n, m));
}
fn read_n_m_k() -> (usize, usize, usize) {
let mut input = String::new();
io::stdin().read_line(&mut input).unwrap();
let parts: Vec<usize> = input
.split_whitespace()
.map(|x| x.parse().unwrap())
.collect();
if let [n, m, k] = &parts[..] {
(*n, *m, *k)
} else {
unreachable!()
}
}
fn read_net_contents(k: usize, net: &mut Net) {
for _ in 0..k {
let mut input = String::new();
io::stdin().read_line(&mut input).unwrap();
let parts: Vec<&str> = input.split_whitespace().collect();
let row: usize = parts[0].parse::<usize>().unwrap() - 1;
let col: usize = parts[1].parse::<usize>().unwrap() - 1;
let val: i32 = match parts[2] {
"H" => 1,
"K" => -10,
_ => unreachable!(),
};
net[row][col] = val
}
}
fn find_max_profit(net: &Net, n: usize, m: usize) -> i32 {
let default_profit: i32 = net.iter().flatten().sum();
let profit_reduction = find_min_reduction(&net, n, m);
default_profit - profit_reduction
}
fn find_min_reduction(net: &Net, n: usize, m: usize) -> i32 {
let max_size = cmp::min(n, m);
cmp::min(
(1..=max_size)
.flat_map(|size| {
(0..=n - size).flat_map(move |rowi| {
(0..=m - size).map(move |coli| {
sum_in_triangle(&net, (rowi, coli), size, TriangleDir::Down)
})
})
})
.min()
.unwrap(),
(1..=max_size)
.flat_map(|size| {
(size - 1..n).flat_map(move |rowi| {
(0..=m - size)
.map(move |coli| sum_in_triangle(&net, (rowi, coli), size, TriangleDir::Up))
})
})
.min()
.unwrap(),
)
}
fn sum_in_triangle(net: &Net, left_corner: (usize, usize), size: usize, dir: TriangleDir) -> i32 {
let (crowi, ccoli) = left_corner;
net.iter()
.enumerate()
.flat_map(|(rowi, row)| {
row.iter()
.enumerate()
.filter(move |(coli, _)| {
is_in_triangle(
crowi as isize,
ccoli as isize,
size as isize,
rowi as isize,
*coli as isize,
dir,
)
})
.map(|(_, val)| val)
})
.sum()
}
fn is_in_triangle(
crowi: isize,
ccoli: isize,
size: isize,
rowi: isize,
coli: isize,
dir: TriangleDir,
) -> bool {
match dir {
TriangleDir::Down => {
rowi >= crowi
&& coli >= ccoli + rowi / 2 - crowi / 2
&& coli < ccoli + size + (crowi + 1) / 2 - (rowi + 1) / 2
}
TriangleDir::Up => {
rowi <= crowi
&& coli >= ccoli + (crowi + 1) / 2 - (rowi + 1) / 2
&& coli < ccoli + size + rowi / 2 - crowi / 2
}
}
}
#[allow(dead_code)]
fn triangle_mask(
net: &Net,
left_corner: (usize, usize),
size: usize,
dir: TriangleDir,
) -> Vec<Vec<i8>> {
let (crowi, ccoli) = left_corner;
net.iter()
.enumerate()
.map(|(rowi, row)| {
row.iter()
.enumerate()
.map(|(coli, _)| {
is_in_triangle(
crowi as isize,
ccoli as isize,
size as isize,
rowi as isize,
coli as isize,
dir,
) as i8
})
.collect()
})
.collect()
}

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:

input
500 500 125000
125 261 K
84 78 K
11 200 K
481 246 K
...

correct output
-624270

user output
(empty)

Test 17

Group: 2

Verdict:

input
500 500 125100
16 61 H
37 62 H
459 125 H
318 476 H
...

correct output
124020

user output
(empty)

Test 18

Group: 2

Verdict:

input
500 500 249999
22 214 H
356 145 H
341 29 H
393 262 H
...

correct output
249999

user output
(empty)

Test 19

Group: 2

Verdict:

input
500 500 32000
30 81 H
315 34 H
78 112 H
367 166 H
...

correct output
10126

user output
(empty)

Test 20

Group: 2

Verdict:

input
500 500 126745
164 390 H
126 331 H
164 126 H
55 92 H
...

correct output
-104692

user output
(empty)

Test 21

Group: 2

Verdict:

input
500 500 71200
106 191 H
314 189 H
482 485 H
344 401 H
...

correct output
-335853

user output
(empty)

Test 22

Group: 2

Verdict:

input
500 500 67772
421 277 H
428 470 H
169 142 H
256 345 H
...

correct output
-208567

user output
(empty)

Test 23

Group: 2

Verdict:

input
500 500 27434
366 481 H
38 22 H
126 107 H
135 169 H
...

correct output
-57100

user output
(empty)

Test 24

Group: 2

Verdict:

input
500 500 93982
183 13 H
463 230 H
264 351 H
399 290 H
...

correct output
-52800

user output
(empty)