CSES - Datatähti 2024 alku - Results
Submission details
Task:Uolevin kalansaalis
Sender:Username*
Submission time:2023-11-01 18:08:55 +0200
Language:C++ (C++20)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#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
#110.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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int ll;
struct Cell {
int row;
int column;
int value;
};
template<typename T>
struct sort_pair {
bool operator()(const pair<int, T>& left, const pair<int, T>& right) {
return left.first < right.first;
}
};
/*template <
class result_t = std::chrono::milliseconds,
class clock_t = std::chrono::steady_clock,
class duration_t = std::chrono::milliseconds
>
auto since(std::chrono::time_point<clock_t, duration_t> const& start)
{
return std::chrono::duration_cast<result_t>(clock_t::now() - start);
}*/
ll answer;
ll totalscore;
ll maxtri = 0;
int main() {
//freopen("input.txt", "r", stdin);
int n, m, k;
cin >> n;
cin >> m;
cin >> k;
vector<pair<int,vector<Cell>>> rows = {}; // vec of rows of cells in order
//auto start = std::chrono::steady_clock::now();
for (int i = 0; i < k; ++i) {
int row, column;
char fish;
cin >> row; row -= 1;
cin >> column; column -= 1;
cin >> fish;
int value;
if (fish == 'K') {
value = 10;
}
else {
value = -1;
}
totalscore -= value;
Cell c;
c.row = row; c.column = column; c.value = value;
pair<int, vector<Cell>> newrow;
newrow.first = row;
newrow.second = { c };
auto it = find_if(rows.begin(), rows.end(),
[&row](const pair<int, vector<Cell>>& element) { return element.first == row; });
if (it != rows.end()) {
it->second.push_back(c);
}
else {
rows.push_back(newrow);
}
}
sort(rows.begin(), rows.end(), sort_pair<vector<Cell>>());
for (pair<int, vector<Cell>> &row : rows) {
sort(row.second.begin(), row.second.end(), [](auto &x, auto &y) { return (x.column < y.column); });
}
bool even = false;
//int debugitercount = 0;
for (int i = 1; i <= n; ++i) { // i, n height
for (int j = 1; j <= m; ++j) { // j, m width
//cout << "\n\nstarting " << i << " " << j;
int maxT, minT;
if (!even) {
maxT = max(0,min({ i - 1, (j - 1) * 3 - 1, (m - j) * 2 + 1 })); // top, left, right
minT = max(0, min({ n - i, (j - 1) * 3 - 1, (m - j) * 2 + 1 })); // bottom, left, right
}
else {
maxT = max(0,min({ i - 1, j * 2 - 1, (m - j) * 3 - 1 })); // top, left, right
minT = max(0,min({ n - i, j * 2 - 1, (m - j) * 3 - 1 })); // bottom, left, right
}
minT = 0-minT;
vector<int> upLines;
vector<int> downLines;
int triSum = 0;
int minX, maxX; minX = maxX = j-1;
//cout << "\n\n Up";
for (int x = 0; x <= maxT; ++x) {
int line = 0;
int rrow = i - x - 1;
bool lineEven = (rrow % 2 == 0);
//cout << "\nRow : " << i - x;
//cout << "\nXrange : " << minX << " - " << maxX;
auto it = find_if(rows.begin(), rows.end(),
[i,rrow](const pair<int, vector<Cell>>& element) { return element.first == rrow; });
if (it != rows.end()) {
for (Cell& cell : it->second) {
if (minX <= cell.column) {
if (cell.column <= maxX) {
line += cell.value;
}
else {
break; // over limit, no more left
}
}
}
}
//cout << "\nline " << line << " at triangle part " << x;
triSum += line;
upLines.push_back(line);
if (lineEven) {
minX -= 1;
}
else {
maxX += 1;
}
}
//cout << "\n-- TRIDONE";
if (triSum > maxtri) {
maxtri = triSum;
//cout << "\n New maxtri " << maxtri << " at " << i << " " << j;
}
for (vector<int>::reverse_iterator it = upLines.rbegin(); it != upLines.rend(); ++it) {
triSum -= *it;
if (triSum > maxtri) {
maxtri = triSum;
//cout << "\n! New maxtri " << maxtri << " at " << i << " " << j;
}
}
//
//
//
//cout << "\n\n Down";
//
//
//
triSum = 0;
minX = maxX = j-1;
for (int x = 0; x >= minT; --x) {
int line = 0;
int rrow = i - x - 1;
bool lineEven = (rrow % 2 == 0);
//cout << "\nRow : " << rrow;
//cout << "\nXrange : " << minX << " - " << maxX;
auto it = find_if(rows.begin(), rows.end(),
[i, rrow](const pair<int, vector<Cell>>& element) { return element.first == rrow; });
if (it != rows.end()) {
for (Cell& cell : it->second) {
if (minX <= cell.column) {
if (cell.column <= maxX) {
line += cell.value;
}
else {
break; // over limit, no more left
}
}
}
}
//cout << "\nline " << line << " at triangle part " << x;
triSum += line;
downLines.push_back(line);
if (lineEven) {
minX -= 1;
}
else {
maxX += 1;
}
}
//cout << "\n-- TRIDONE";
if (triSum > maxtri) {
maxtri = triSum;
//cout << "\n New maxtri " << maxtri << " at " << i << " " << j;
}
for (vector<int>::reverse_iterator it = downLines.rbegin(); it != downLines.rend(); ++it) {
triSum -= *it;
if (triSum > maxtri) {
maxtri = triSum;
//cout << "\n! New maxtri " << maxtri << " at " << i << " " << j;
}
}
}
//cout << "\n " << maxtri;
even = !even;
}
//cout << debugitercount;
//cout << "\n-- THE END --\nElapsed (ms)=" << since(start).count() << endl;
//cout << "\n\nRowsize: " << rows.size() << " \nTotalscore: " << totalscore << "\nMaxtri: " << maxtri << "\n\n";
answer = totalscore + maxtri;
cout << answer << "\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:

input
1 1 1
1 1 H

correct output
0

user output
1

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)