CSES - Datatähti 2024 alku - Results
Submission details
Task:Uolevin kalansaalis
Sender:rottis
Submission time:2023-11-12 22:43:07 +0200
Language:C++ (C++20)
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.01 s1, 2details
#15ACCEPTED0.01 s1, 2details
#16--2details
#17--2details
#18--2details
#19--2details
#20--2details
#21--2details
#22--2details
#23--2details
#24--2details

Code

/*def legal_triangle(y, x, size, dir, height, width) # dir = -1 or 1 # O(1)
return x >= 0 &&
(x + size) <= (width) &&
(y + (dir * size) + 1) >= 0 &&
(y + (dir * size)) <= height
end*/
#include <iostream>
#include <cmath>
#include <vector>
#include <array>
bool legal_triangle(int y, int x, int size, int dir, int height, int width) {
return (x >= 0) &&
((x + size) <= width) &&
((y + (dir * size) + 1) >= 0) &&
((y + (dir * size)) <= height);
}
/*def in_triangle(tri_y, tri_x, tri_size, tri_dir, cell_y, cell_x) # O(1)
tri_y2 = tri_y + tri_size * tri_dir
offset = ((((tri_y) % 2 == 1) && ((cell_y) % 2 == 0)) ? -1 : 0)
if tri_dir == 1
dy = (tri_y - cell_y) / 2.0
dyl = dy.ceil.to_i
dyr = dy.floor.to_i
return (tri_y <= cell_y && cell_y < tri_y2) && # dir = 1
(tri_x - offset) <= (cell_x + dyl) && # both
(cell_x + offset) < (tri_x + (tri_size + dyr)) # both
else
dy = (cell_y - tri_y) / 2.0
dyl = dy.ceil.to_i
dyr = dy.floor.to_i
return (tri_y2 <= cell_y && cell_y <= tri_y) && # dir = -1
(tri_x - offset) <= (cell_x + dyl) && # both
(cell_x + offset) < (tri_x + (tri_size + dyr)) # both
end
end*/
bool in_triangle(int tri_y, int tri_x, int tri_size, int tri_dir, int cell_y, int cell_x) {
int tri_y2 = tri_y + tri_size * tri_dir;
int offset = ((((tri_y) % 2 == 1) && ((cell_y) % 2 == 0)) ? -1 : 0);
float dy;
int dyl, dyr;
if (tri_dir == 1) {
dy = (tri_y - cell_y) / 2.0;
dyl = (int) ceil(dy);
dyr = (int) floor(dy);
return (tri_y <= cell_y && cell_y < tri_y2) &&
((tri_x - offset) <= (cell_x + dyl)) &&
((cell_x + offset) < (tri_x + (tri_size + dyr)));
} else {
dy = (cell_y - tri_y) / 2.0;
dyl = (int) ceil(dy);
dyr = (int) floor(dy);
return (tri_y2 <= cell_y && cell_y <= tri_y) &&
((tri_x - offset) <= (cell_x + dyl)) &&
((cell_x + offset) < (tri_x + (tri_size + dyr)));
}
}
/*
def get_value(y, x, size, dir, fishies)
val = 0
fishies.each do |fish|
if in_triangle(y, x, size, dir, fish[0], fish[1])
val += fish[2]
#print("#{fish} is in tri")
end
end
return val # total - val for true value
end
*/
int get_value(int y, int x, int size, int dir, std::vector<std::array<int, 3>> *fishies) {
int val = 0;
std::array<int, 3> fish;
for (long unsigned int i = 0; i < fishies->size(); i++) {
fish = fishies->at(i);
if (in_triangle(y, x, size, dir, fish[0], fish[1])) {
val += fish[2];
}
}
return val;
}
int main() {
int height, width, count;
std::cin >> height >> width >> count;
std::vector<std::array<int, 3>> fishies;
int total = 0;
int min_size = ((height <= 10) ? 1 : 10);
int y, x, t;
char ct;
std::array<int, 3> temp;
for (int i = 0; i < count; i++) {
std::cin >> y >> x >> ct;
t = ((ct == 'H') ? 1 : -10);
temp[0] = y - 1;
temp[1] = x - 1;
temp[2] = t;
fishies.push_back(temp);
total += t;
}
int size, dir;
bool legal, c;
int min_value = 2147483640;
int value;
for (int y = 0; y < height; y++) {
for (int x = 0; x < 9; x++) {
size = min_size;
dir = -1;
c = true;
while (c) {
legal = legal_triangle(y, x, size, dir, height, width);
if (legal) {
value = get_value(y, x, size, dir, &fishies);
if (min_value > value) {
min_value = value;
}
size += 1;
} else {
if (dir == -1) {
size = min_size;
dir = 1;
} else {
c = false;
}
}
}
}
}
std::cout << total - min_value;
return 0;
}
/*
height, width, count = gets.chomp.split(" ").map(&:to_i)
fishies = []
total = 0
min_size = (height <= 10 ? 1 : 10)
count.times do
y, x, t = gets.chomp.split(" ")
t = (t == "H" ? 1 : -10)
fishies << [y.to_i-1, x.to_i-1, t]
total += t
end
values = []
(0...height).each do |y|
(0...width).each do |x|
size = min_size
dir = -1
continue = true
while continue
legal = legal_triangle(y, x, size, dir, height, width)
if legal
values << get_value(y, x, size, dir, fishies)
size += 1
#puts total - values[-1]
else
if dir == -1
size = min_size
dir = 1
else
continue = false
end
end
end
end
end
puts(total - values.min)
*/

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)