Task: | Uolevin kalansaalis |
Sender: | rottis |
Submission time: | 2023-11-12 22:43:07 +0200 |
Language: | C++ (C++20) |
Status: | READY |
Result: | 37 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 37 |
#2 | TIME LIMIT EXCEEDED | 0 |
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.01 s | 1, 2 | details |
#15 | ACCEPTED | 0.01 s | 1, 2 | details |
#16 | TIME LIMIT EXCEEDED | -- | 2 | details |
#17 | TIME LIMIT EXCEEDED | -- | 2 | details |
#18 | TIME LIMIT EXCEEDED | -- | 2 | details |
#19 | TIME LIMIT EXCEEDED | -- | 2 | details |
#20 | TIME LIMIT EXCEEDED | -- | 2 | details |
#21 | TIME LIMIT EXCEEDED | -- | 2 | details |
#22 | TIME LIMIT EXCEEDED | -- | 2 | details |
#23 | TIME LIMIT EXCEEDED | -- | 2 | details |
#24 | TIME LIMIT EXCEEDED | -- | 2 | details |
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)) <= heightend*/#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_diroffset = ((((tri_y) % 2 == 1) && ((cell_y) % 2 == 0)) ? -1 : 0)if tri_dir == 1dy = (tri_y - cell_y) / 2.0dyl = dy.ceil.to_idyr = dy.floor.to_ireturn (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)) # bothelsedy = (cell_y - tri_y) / 2.0dyl = dy.ceil.to_idyr = dy.floor.to_ireturn (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)) # bothendend*/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 = 0fishies.each do |fish|if in_triangle(y, x, size, dir, fish[0], fish[1])val += fish[2]#print("#{fish} is in tri")endendreturn val # total - val for true valueend*/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 = 0min_size = (height <= 10 ? 1 : 10)count.times doy, x, t = gets.chomp.split(" ")t = (t == "H" ? 1 : -10)fishies << [y.to_i-1, x.to_i-1, t]total += tendvalues = [](0...height).each do |y|(0...width).each do |x|size = min_sizedir = -1continue = truewhile continuelegal = legal_triangle(y, x, size, dir, height, width)if legalvalues << get_value(y, x, size, dir, fishies)size += 1#puts total - values[-1]elseif dir == -1size = min_sizedir = 1elsecontinue = falseendendendendendputs(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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
input |
---|
500 500 93982 183 13 H 463 230 H 264 351 H 399 290 H ... |
correct output |
---|
-52800 |
user output |
---|
(empty) |