CSES - Datatähti 2024 alku - Results
Submission details
Task:Uolevin kalansaalis
Sender:andreibe
Submission time:2023-10-30 23:43:56 +0200
Language:C++ (C++11)
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED37
#2ACCEPTED63
Test results
testverdicttimegroup
#1ACCEPTED0.04 s1, 2details
#2ACCEPTED0.04 s1, 2details
#3ACCEPTED0.04 s1, 2details
#4ACCEPTED0.04 s1, 2details
#5ACCEPTED0.04 s1, 2details
#6ACCEPTED0.04 s1, 2details
#7ACCEPTED0.04 s1, 2details
#8ACCEPTED0.04 s1, 2details
#9ACCEPTED0.04 s1, 2details
#10ACCEPTED0.04 s1, 2details
#11ACCEPTED0.04 s1, 2details
#12ACCEPTED0.04 s1, 2details
#13ACCEPTED0.04 s1, 2details
#14ACCEPTED0.04 s1, 2details
#15ACCEPTED0.04 s1, 2details
#16ACCEPTED0.75 s2details
#17ACCEPTED0.75 s2details
#18ACCEPTED0.81 s2details
#19ACCEPTED0.70 s2details
#20ACCEPTED0.75 s2details
#21ACCEPTED0.72 s2details
#22ACCEPTED0.72 s2details
#23ACCEPTED0.70 s2details
#24ACCEPTED0.73 s2details

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-right
for (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-right
for (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-left
for (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;
}
}
// rows
for (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++)
{
// down
ll maxKDown = m + 1 - x;
maxKDown = min(maxKDown, n + 1 - y);
// up
ll 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