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

Code

# lines - can address by coord and size
all_lines = {}
# triangles - can address by coord, size, is_down
all_triangles = {}
def get_all_inputs_and_field():
n, m, k = [int(el) for el in input().split()]
field = {}
total_field_value = 0
for i in range(k):
x,y,catch = [el for el in input().split()]
x = int(x)
y = int(y)
coins = 0
if catch == 'K':
coins = -10
elif catch == 'H':
coins = 1
field[x, y] = coins
total_field_value += coins
# print(n,m,k,field,total_field_value)
return n,m,k,field,total_field_value
n,m,k,field,total_field_value = get_all_inputs_and_field()
def calculate_all_valid_lines(size):
for x in range(1, n+1):
for y in range(1, m + 2 - size):
if size==2:
line_value = field.get((x, y), 0) + field.get((x, y + 1), 0)
all_lines[(x, y, size)] = line_value
if size > 2:
all_lines[(x, y, size)] = all_lines[(x, y, size - 1)] + field.get((x, y + size -1), 0)
def get_line_value(x, y, size):
if size >= 2:
return all_lines[(x, y, size)]
else:
return field.get((x, y), 0)
def calculate_all_valid_down_triangles(size):
# generate down triangles
is_down = 1
for x in range(1, n+2-size):
for y in range(1, m + 2 - size):
curr_triangle_value = get_line_value(x, y, size)
# if (x ==2 and y==3 and size ==4):
# print(curr_triangle_value)
next_line_size = size - 1
next_line_x = x + 1
if x % 2 == 0:
next_line_y = y + 1
else:
next_line_y = y
while next_line_size > 0:
curr_triangle_value += get_line_value(next_line_x, next_line_y, next_line_size)
# if (x ==2 and y==3 and size == 4):
# print(curr_triangle_value)
# print(f"{next_line_x}, {next_line_y}, {next_line_size}")
next_line_size = next_line_size - 1
if next_line_x % 2 == 0:
next_line_y = next_line_y + 1
next_line_x = next_line_x + 1
all_triangles[(x, y, size, is_down)] = curr_triangle_value
def calculate_all_valid_up_triangles(size):
is_down = 0
for x in range(n, size-1, -1):
for y in range(1, m + 2 - size):
# print(f"{x}, {y}")
curr_triangle_value = get_line_value(x, y, size)
# if (x ==4 and y==3 and size ==4):
# print(curr_triangle_value)
next_line_size = size - 1
next_line_x = x - 1
if x % 2 == 0:
next_line_y = y + 1
else:
next_line_y = y
while next_line_size > 0:
curr_triangle_value += get_line_value(next_line_x, next_line_y, next_line_size)
# if (x ==4 and y==3 and size == 4):
# print(curr_triangle_value)
# print(f"{next_line_x}, {next_line_y}, {next_line_size}")
next_line_size = next_line_size - 1
if next_line_x % 2 == 0:
next_line_y = next_line_y + 1
next_line_x = next_line_x - 1
all_triangles[(x, y, size, is_down)] = curr_triangle_value
# In[304]:
def main():
current_best_triangle = None
# calculate best result with triangle of size one
for key,value in field.items():
if current_best_triangle is None:
# print("is none found")
current_best_triangle = value
if current_best_triangle > value:
current_best_triangle = value
if value == -10:
break
if current_best_triangle is None:
# only empty cells presented
current_best_triangle = 0
if current_best_triangle > 0 and k != len(field):
# we'd better remove empty triangle
current_best_triangle = 0
# print(f"current best triangle after checking for size 1 triangles: {current_best_triangle}")
# case with all pikes
# if k == len(field) and current_best_triangle is None:
# current_best_triangle = 1
# print("Best result with size 1: " + total_field_value - current_best_triangle)
# return
# else:
max_size_triangle = min(n, m)
for size in range(2, max_size_triangle + 1):
calculate_all_valid_lines(size)
for size in range(2, max_size_triangle + 1):
calculate_all_valid_down_triangles(size)
for size in range(2, max_size_triangle + 1):
calculate_all_valid_up_triangles(size)
for key, value in all_triangles.items():
if current_best_triangle > value:
current_best_triangle = value
# print(f"current best triangle: {current_best_triangle}")
# print(f"total_field_value {total_field_value}")
best_result = total_field_value - current_best_triangle
print(best_result)
# In[305]:
main()

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)