Task: | Uolevin kalansaalis |
Sender: | stpn129 |
Submission time: | 2023-11-01 10:14:24 +0200 |
Language: | C++ (C++17) |
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.00 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
#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_JUDGEfreopen("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) {//upint 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);}//downint 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: 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) |