Task: | Uolevin kalansaalis |
Sender: | chaotic |
Submission time: | 2023-11-08 22:10:53 +0200 |
Language: | C++ (C++20) |
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.40 s | 2 | details |
#17 | ACCEPTED | 0.40 s | 2 | details |
#18 | ACCEPTED | 0.47 s | 2 | details |
#19 | ACCEPTED | 0.35 s | 2 | details |
#20 | ACCEPTED | 0.40 s | 2 | details |
#21 | ACCEPTED | 0.37 s | 2 | details |
#22 | ACCEPTED | 0.37 s | 2 | details |
#23 | ACCEPTED | 0.35 s | 2 | details |
#24 | ACCEPTED | 0.39 s | 2 | details |
Code
#include <algorithm>#include <cassert>#include <iostream>#include <limits>#include <sstream>#include <vector>static_assert(sizeof(int) == 4);template<class T> struct array2d {std::vector<T> data;size_t const rows;size_t const cols;constexpr array2d(size_t rows_, size_t cols_): data(rows_ * cols_, 0), rows(rows_), cols(cols_) {}constexpr T& operator()(size_t row, size_t col) {assert(row < rows);assert(col < cols);return data[row + col * rows];}constexpr T const& operator()(size_t row, size_t col) const {assert(row < rows);assert(col < cols);return data[row + col * rows];}};// Calculate sum in range [first, first + count)int sum_between(auto const& arr, size_t row, size_t first, size_t count) {return arr(row, first + count) - arr(row, first);}auto create_diagonals(auto const& values, int const first_row_offset) {array2d<int> arr(values.rows + 1, values.cols + (values.rows - first_row_offset) / 2);auto col_of_next_row = [first_row_offset](size_t row, size_t col) {if (first_row_offset == 0) return row % 2 == 1 ? col : col - 1;return row % 2 == 0 ? col : col - 1;};auto colum_starting_at = [&](size_t row, size_t col) {assert(row == 0 || col == values.cols - 1);size_t const target_col = row == 0 ? col : values.cols + (row - first_row_offset) / 2;size_t target_row = row + 1;// arr(target_row++, target_col) = 0;while (true) {if (row >= values.rows) break;if (col + 1 == 0) break;arr(target_row, target_col) = arr(target_row - 1, target_col) + values(row, col);col = col_of_next_row(row, col);++row;++target_row;}};for (size_t col = 0; col < values.cols; ++col) colum_starting_at(0, col);for (size_t row = 1 + first_row_offset; row < values.rows; row += 2)colum_starting_at(row, values.cols - 1);return arr;}int get_diagonal_sum(auto const& diagonals, size_t row, size_t col, size_t count, int const first_row_offset) {size_t target_column;if (first_row_offset == 0) {target_column = col + (row + 1) / 2;} else {target_column = col + row / 2;}return diagonals(row + count, target_column) - diagonals(row, target_column);}int do_search(int total, size_t const rows, size_t const cols, auto const& values, auto const& diags,int const first_row_offset) {int result = std::numeric_limits<int>::min();size_t const biggest_triangle = std::min(rows, cols);for (size_t row = 0; row < rows; ++row) {for (size_t col = 0; col < cols; ++col) {int sum = values(row, col);result = std::max(result, total - sum);// if (col == 2 && row == 1) asm("int $3");for (size_t T = 2; T <= biggest_triangle; ++T) {if (row + T > rows) break;if (col + T > cols) break;sum += get_diagonal_sum(diags, row, col + T - 1, T, first_row_offset);result = std::max(result, total - sum);}}}return result;}int main() {// std::stringstream input(R"(5 6 13// 1 1 K// 5 1 K// 2 2 H// 4 2 H// 5 2 H// 2 6 K// 3 3 H// 3 4 K// 3 5 H// 3 6 K// 4 4 K// 2 5 H// 5 5 H)");// std::stringstream input(R"(// 4 4 4// 1 1 H// 3 3 K// 4 2 K// 4 3 K// )");auto& input = std::cin;size_t rows, cols, k;input >> rows >> cols >> k;array2d<int> values(rows, cols);int total_sum = 0;for (size_t i = 0; i < k; ++i) {size_t x, y;char ch;input >> x >> y >> ch;values(x - 1, y - 1) = ch == 'K' ? -10 : 1;total_sum += ch == 'K' ? -10 : 1;}// ---------------------auto diags = create_diagonals(values, 0);int result = do_search(total_sum, rows, cols, values, diags, 0);// Reverse each columnfor (size_t i = 0; i < cols; ++i) { std::reverse(&values(0, i), &values(rows - 1, i) + 1); }int const first_row_offset = rows % 2 == 0 ? 1 : 0;auto diags2 = create_diagonals(values, first_row_offset);result = std::max(result, do_search(total_sum, rows, cols, values, diags2, first_row_offset));std::cout << result << "\n";}
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 |