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

Code

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
void init_code() {
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
inline vector<pair<int, int>> adj(pair<int, int> cell) {
vector<pair<int, int>> res;
int i = cell.first, j = cell.second;
if (i % 2 == 0) {
res = {{i, j - 1}, {i - 1, j}, {i - 1, j + 1}, {i, j + 1}, {i + 1, j + 1}, {i + 1, j}};
} else {
res = {{i, j - 1}, {i - 1, j - 1}, {i - 1, j}, {i, j + 1}, {i + 1, j}, {i + 1, j - 1}};
}
return res;
}
inline bool ok(pair<int, int> cell, int n, int m) {
return cell.first >= 1 && cell.first <= n && cell.second >= 1 && cell.second <= m;
}
inline pair<int, int> aj(pair<int, int> cell, int idx) {
int i = cell.first, j = cell.second;
if (i % 2 == 0) {
if (idx == 0) return {i, j - 1};
if (idx == 1) return {i - 1, j};
if (idx == 2) return {i - 1, j + 1};
if (idx == 3) return {i, j + 1};
if (idx == 4) return {i + 1, j + 1};
if (idx == 5) return {i + 1, j};
}
if (idx == 0) return {i, j - 1};
if (idx == 1) return {i - 1, j - 1};
if (idx == 2) return {i - 1, j};
if (idx == 3) return {i, j + 1};
if (idx == 4) return {i + 1, j};
return {i + 1, j - 1};
}
const int inf = 1e9;
void solve() {
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> g(n + 1, vector<int> (m + 1, 0));
int s = 0;
for (int i = 1; i <= k; ++i) {
int a, b;
cin >> a >> b;
char c;
cin >> c;
if (c == 'H') {
g[a][b] = 1;
} else {
g[a][b] = -10;
}
s += g[a][b];
}
vector<vector<int>> p1(n + 1, vector<int> (m + 1, 0));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
p1[i][j] += g[i][j];
pair<int, int> a_0 = aj({i, j}, 0);
pair<int, int> a_1 = aj({i, j}, 1);
pair<int, int> a_1_0 = aj(a_1, 0);
if (ok(a_0, n, m))
p1[i][j] += p1[a_0.first][a_0.second];
if (ok(a_1, n, m))
p1[i][j] += p1[a_1.first][a_1.second];
if (ok(a_1_0, n, m))
p1[i][j] -= p1[a_1_0.first][a_1_0.second];
}
}
vector<vector<int>> p2(n + 1, vector<int> (m + 1, 0));
for (int i = 1; i <= n; ++i) {
for (int j = m; j >= 1; --j) {
pair<int, int> a_2 = aj({i, j}, 2);
pair<int, int> a_3 = aj({i, j}, 3);
pair<int, int> a_2_3 = aj(a_2, 3);
p2[i][j] += g[i][j];
if (ok(a_2, n, m))
p2[i][j] += p2[a_2.first][a_2.second];
if (ok(a_3, n, m))
p2[i][j] += p2[a_3.first][a_3.second];
if (ok(a_2_3, n, m))
p2[i][j] -= p2[a_2_3.first][a_2_3.second];
}
}
vector<vector<int>> p3(n + 1, vector<int> (m + 1, 0));
for (int i = n; i >= 1; --i) {
for (int j = 1; j <= m; ++j) {
pair<int, int> a_0 = aj({i, j}, 0);
pair<int, int> a_5 = aj({i, j}, 5);
pair<int, int> a_5_0 = aj(a_5, 0);
p3[i][j] += g[i][j];
if (ok(a_0, n, m))
p3[i][j] += p3[a_0.first][a_0.second];
if (ok(a_5, n, m))
p3[i][j] += p3[a_5.first][a_5.second];
if (ok(a_5_0, n, m))
p3[i][j] -= p3[a_5_0.first][a_5_0.second];
}
}
vector<vector<int>> p4(n + 1, vector<int> (m + 1, 0));
for (int i = n; i >= 1; --i) {
for (int j = m; j >= 1; --j) {
pair<int, int> a_3 = aj({i, j}, 3);
pair<int, int> a_4 = aj({i, j}, 4);
pair<int, int> a_4_3 = aj(a_4, 3);
p4[i][j] += g[i][j];
if (ok(a_3, n, m))
p4[i][j] += p4[a_3.first][a_3.second];
if (ok(a_4, n, m))
p4[i][j] += p4[a_4.first][a_4.second];
if (ok(a_4_3, n, m))
p4[i][j] -= p4[a_4_3.first][a_4_3.second];
}
}
vector<int> p0(n + 1), p5(n + 2);
for (int i = 1; i <= n; ++i) {
p0[i] += p0[i - 1];
for (int j = 1; j <= m; ++j) {
p0[i] += g[i][j];
}
p5[n - i + 1] += s - p0[i - 1];
}
int mn = inf;
int t_max = min(n, m);
for (int t = 1; t <= t_max; ++t) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
//up
int ux1 = i + t - 1, uy1, ux2 = i + t - 1, uy2;
if (i % 2 == 1) {
uy2 = j + (t - 1) / 2;
uy1 = uy2 - (t - 1);
} else {
uy1 = j - (t - 1) / 2;
uy2 = uy1 + (t - 1);
}
if (ok({ux1, uy1}, n, m) && ok({ux2, uy2}, n, m)) {
int tmp = s;
tmp -= p0[i - 1];
tmp -= p5[n - ux1];
int x = 0;
pair<int, int> v0_0 = aj({i, j}, 0);
if (ok(v0_0, n, m)) {
x += p3[v0_0.first][v0_0.second];
}
pair<int, int> v1_0_5 = aj(aj({ux1, uy1}, 0), 5);
if (ok(v1_0_5, n, m)) {
x -= p3[v1_0_5.first][v1_0_5.second];
}
tmp -= x;
int y = 0;
pair<int, int> v0_3 = aj({i, j}, 3);
if (ok(v0_3, n, m)) {
y += p4[v0_3.first][v0_3.second];
}
pair<int, int> v2_3_4 = aj(aj({ux2, uy2}, 3), 4);
if (ok(v2_3_4, n, m)) {
y -= p4[v2_3_4.first][v2_3_4.second];
}
tmp -= y;
//cout << t << ' ' << ux1 << ' ' << uy1 << ' ' << tmp << '\n';
mn = min(mn, tmp);
}
//down
int px1 = i - (t - 1), py1, px2 = i - (t - 1), py2;
if (i % 2 == 1) {
py2 = j + (t - 1) / 2;
py1 = py2 - (t - 1);
} else {
py1 = j - (t - 1) / 2;
py2 = py1 + (t - 1);
}
if (ok({px1, py1}, n, m) && ok({px2, py2}, n, m)) {
int tmp = s;
tmp -= p0[px1 - 1];
tmp -= p5[n - i];
vector<pair<int, int>> a0 = adj({i, j}), a1 = adj({px1, py1}),
a2 = adj({px2, py2});
vector<pair<int, int>> a_a1 = adj(a1[0]), a_a2 = adj(a2[3]);
int x = 0;
if (ok(a0[0], n, m)) {
x += p1[a0[0].first][a0[0].second];
}
if (ok(a_a1[1], n, m)) {
x -= p1[a_a1[1].first][a_a1[1].second];
}
tmp -= x;
int y = 0;
if (ok(a0[3], n, m)) {
y += p2[a0[3].first][a0[3].second];
}
if (ok(a_a2[2], n, m)) {
y -= p2[a_a2[2].first][a_a2[2].second];
}
tmp -= y;
//cout << t << ' ' << ux1 << ' ' << uy1 << ' ' << tmp << '\n';
mn = min(mn, tmp);
}
}
}
}
cout << s - mn << '\n';
}
signed main() {
init_code();
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}

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)