Task: | Uolevin kalansaalis |
Sender: | andreibe |
Submission time: | 2023-10-30 23:43:56 +0200 |
Language: | C++ (C++11) |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 37 |
#2 | ACCEPTED | 63 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.04 s | 1, 2 | details |
#2 | ACCEPTED | 0.04 s | 1, 2 | details |
#3 | ACCEPTED | 0.04 s | 1, 2 | details |
#4 | ACCEPTED | 0.04 s | 1, 2 | details |
#5 | ACCEPTED | 0.04 s | 1, 2 | details |
#6 | ACCEPTED | 0.04 s | 1, 2 | details |
#7 | ACCEPTED | 0.04 s | 1, 2 | details |
#8 | ACCEPTED | 0.04 s | 1, 2 | details |
#9 | ACCEPTED | 0.04 s | 1, 2 | details |
#10 | ACCEPTED | 0.04 s | 1, 2 | details |
#11 | ACCEPTED | 0.04 s | 1, 2 | details |
#12 | ACCEPTED | 0.04 s | 1, 2 | details |
#13 | ACCEPTED | 0.04 s | 1, 2 | details |
#14 | ACCEPTED | 0.04 s | 1, 2 | details |
#15 | ACCEPTED | 0.04 s | 1, 2 | details |
#16 | ACCEPTED | 0.75 s | 2 | details |
#17 | ACCEPTED | 0.75 s | 2 | details |
#18 | ACCEPTED | 0.81 s | 2 | details |
#19 | ACCEPTED | 0.70 s | 2 | details |
#20 | ACCEPTED | 0.75 s | 2 | details |
#21 | ACCEPTED | 0.72 s | 2 | details |
#22 | ACCEPTED | 0.72 s | 2 | details |
#23 | ACCEPTED | 0.70 s | 2 | details |
#24 | ACCEPTED | 0.73 s | 2 | details |
Code
#include <iostream>#include <string>#include <math.h>#include <map>#include <algorithm>#include <vector>#include <fstream>#include <set>#include <unordered_map>#include <queue>#include <chrono>#include <climits>#include <stack>using namespace std;using namespace std::chrono;typedef long long ll;typedef unsigned long long ull;typedef pair<ll, ll> P;#define S second#define F first// #define A 999999999999999999LL#define M 1000000007#define N 202020#define REDIR \ifstream in("input.txt"); \cin.rdbuf(in.rdbuf());ll ar[550][550];ll rows[550][550];ll diagonals[550][550];ll diagonals2[550][550];ll n, m, k;ll getVal(ll y, ll x){if (y < 0 || x < 0)return 0;return rows[y][x];}ll alasKolmio(ll y, ll x, ll k){ll sumRowSmallerX = y % 2 == 1 ? x - 1 - 1 : x - 1;ll sumRowSmallerY = y - 1;ll rowSumSmaller = getVal(sumRowSmallerY, sumRowSmallerX);ll sumRowLargerX = y % 2 == 1 ? (x - 1 + k - 1) : (x + k - 1);ll sumRowLargerY = y - 1;ll rowSumLarger = getVal(sumRowLargerY, sumRowLargerX);ll minDiagonalX = x + k - 1 + (y % 2 == 0 ? 1 : 0);ll minDiagonalY = y - 1;ll diagonalSmaller = diagonals2[minDiagonalY][minDiagonalX];ll maxDiagonalX = x + (y % 2 == 1 ? (k / 2 - 1 + k % 2) : (k / 2));ll maxDiagonalY = y + k - 1;ll diagonalLarger = diagonals2[maxDiagonalY][maxDiagonalX];ll result = (diagonalLarger - diagonalSmaller) - (rowSumLarger - rowSumSmaller);return result;}ll ylosKolmio(ll y, ll x, ll k){ll rowSumSmaller = rows[y][x - 1];ll rowSumLarger = rows[y][x + k - 1];bool parillinen = (y % 2 == 0);ll minDiagonalX = x + (parillinen ? (k / 2) : (k / 2 - 1 + k % 2));ll diagonalSmaller = y - k - 1 < 0 ? 0 : diagonals2[y - k - 1][minDiagonalX];ll diagonalLarger = diagonals2[y - 1][x + (parillinen ? 0 : -1)];ll result = (rowSumLarger - rowSumSmaller) - (diagonalLarger - diagonalSmaller);return result;}int main(){cin >> n >> m >> k;ll kokonaismaara = 0;for (ll i = 0; i < k; i++){ll a, b;char c;cin >> a >> b >> c;ar[a][b] = c == 'K' ? -10 : 1;kokonaismaara += ar[a][b];}ll L = 2520;// down left-rightfor (ll sy = 1; sy <= L; sy += 2){ll summa = 0;ll x = 0;for (ll y = sy; y <= L; y++){if (y % 2 == 1)x++;if (y >= 550 || x >= 550)continue;summa += ar[y][x];diagonals[y][x] = summa;}}// right left-rightfor (ll sx = 1; sx <= L; sx++){ll summa = 0;ll x = sx;for (ll y = 1; y <= L; y++){if (y % 2 == 1)x++;if (y >= 550 || x >= 550)continue;summa += ar[y][x];diagonals[y][x] = summa;}}// right right-leftfor (ll sx = 1; sx <= L; sx++){ll x = sx;ll summa = 0;for (ll y = 1; y <= L; y++){if (y % 2 == 0)x--;if (y >= 550 || x >= 550)continue;if (x < 0 || y < 0)continue;summa += diagonals[y][x];diagonals2[y][x] = summa;}}// rowsfor (ll y = 0; y <= L; y++){ll summa = 0;for (ll x = 0; x <= L; x++){if (y >= 550 || x >= 550)continue;summa += diagonals[y][x];rows[y][x] = summa;}}// System.out.prllln("Preparing done " + n + " " + m);// prll();ll minSum = 999999999;for (ll y = 1; y <= n; y++){// System.out.prllln("Y" + y);for (ll x = 1; x <= m; x++){// downll maxKDown = m + 1 - x;maxKDown = min(maxKDown, n + 1 - y);// upll maxKUp = m + 1 - x;maxKUp = min(maxKUp, y);ll maxK = max(maxKDown, maxKUp);for (ll k = 1; k <= maxK; k++){ll result;if (k <= maxKDown){result = k == 1 ? ar[y][x] : alasKolmio(y, x, k);minSum = min(minSum, result);}if (k <= maxKUp){result = k == 1 ? ar[y][x] : ylosKolmio(y, x, k);minSum = min(minSum, result);}}}}cout << (kokonaismaara - minSum);}
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 |