CSES - Datatähti 2024 alku - Results
Submission details
Task:Uolevin kalansaalis
Sender:adex720
Submission time:2023-11-05 15:49:38 +0200
Language:C++ (C++17)
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED37
#2ACCEPTED63
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
#16ACCEPTED0.28 s2details
#17ACCEPTED0.28 s2details
#18ACCEPTED0.13 s2details
#19ACCEPTED0.23 s2details
#20ACCEPTED0.28 s2details
#21ACCEPTED0.25 s2details
#22ACCEPTED0.26 s2details
#23ACCEPTED0.23 s2details
#24ACCEPTED0.27 s2details

Code

#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio();
cin.tie(nullptr);
int n, m, k, x, y, arvo, pienempi;
cin >> n >> m >> k;
pienempi = min(n, m);
if (k == 0)
{
cout << 0;
return 0;
}
int arvot[n][m];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
arvot[i][j] = 0;
}
}
int arvoYhteensa = 0;
string kala;
bool rapuja = false; // MUUTA SAKISDKFAISIFpHI
bool onkoHauki;
if (true)
for (int i = 0; i < k; i++)
{
cin >> y >> x;
x--;
y--;
cin >> kala;
onkoHauki = kala[0] == 'H';
if (!onkoHauki)
rapuja = true;
arvo = onkoHauki ? 1 : -10;
arvot[y][x] = arvo;
arvoYhteensa += arvo;
}
if (!rapuja)
{
if (k == n * m)
{
cout << arvoYhteensa - 1;
}
else
{
cout << arvoYhteensa;
}
return 0;
}
if (pienempi == 1)
{
if (n == 1 && m == 1)
{
cout << 0;
}
else
{
cout << arvoYhteensa + 10;
}
return 0;
}
int alas = (n - 1) / 2;
int vinoja = m + alas;
int summatAlas[n][m];
int summatYlos[n][m];
int summa;
int alku = 2 * alas;
int raja = 0;
int uusiX;
for (int x = 0; x < vinoja; x++)
{
summa = 0;
alku = min(n - 1, 2 * x);
raja = max(0, (x - m) * 2 + 1);
uusiX = max(0, x - alas - ((n + 1) & 1));
for (int y = alku; y >= raja; y--)
{
summa += arvot[y][uusiX];
summatYlos[y][uusiX] = summa;
//cout << uusiX << ", " << y << " = " << summa << "\n";
uusiX += y & 1;
}
}
summatYlos[n - 1][m - 1] = arvot[n - 1][m - 1];
raja = n;
for (int x = 0; x <= vinoja; x++)
{
summa = 0;
alku = max(0, (n - 2 * x - 2 + (n & 1)));
raja = min(n - 1, n - (x - m + 1) * 2 - ((n + 1) & 1));
uusiX = max(0, x - alas);
for (int y = alku; y <= raja; y++)
{
// cout << uusiX << ", " << y << "\n";
summa += arvot[y][uusiX];
summatAlas[y][uusiX] = summa;
//cout << uusiX << ", " << y << " = " << summa << "\n";
uusiX += y & 1;
}
}
if (!(n & 1))
{
summa = arvot[0][m - 1];
summatAlas[0][m - 1] = summa;
summa += arvot[1][m - 1];
summatAlas[1][m - 1] = summa;
}
int minimi = -10;
int nykyinenArvo;
int alkuarvo;
int kokoM1;
int huipunXkorjaus;
for (int y = 0; y < n - 1; y++)
{
alkuarvo = arvot[y][0];
kokoM1 = 0;
for (int koko = 2; koko <= n - y && koko <= m; koko++)
{
kokoM1++;
huipunXkorjaus = (koko - 1 + (y & 1)) >> 1;
if (y + koko < n)
{
int oikeaX = koko == 2 ? 0 : (koko - 2 + (y & 1)) >> 1;
alkuarvo += summatYlos[y][kokoM1] - summatYlos[y + koko][oikeaX];
}
else
alkuarvo += summatYlos[y][kokoM1];
nykyinenArvo = alkuarvo;
//cout << nykyinenArvo << "\n";
if (nykyinenArvo < minimi)
{
minimi = nykyinenArvo;
}
raja = m - koko;
for (int x = 1; x <= raja; x++)
{
nykyinenArvo += summatYlos[y][kokoM1 + x] - summatAlas[y + kokoM1][huipunXkorjaus + x - 1];
if (y > 0 && (x > 1 || (y & 1)))
nykyinenArvo += summatAlas[y - 1][x - 1 - ((y + 1) & 1)];
if (y + koko < n)
nykyinenArvo -= summatYlos[y + koko][huipunXkorjaus + x - ((y + koko) & 1)];
//cout << nykyinenArvo << "\n";
if (nykyinenArvo < minimi)
{
minimi = nykyinenArvo;
}
}
}
}
for (int y = n - 1; y > 0; y--)
{
alkuarvo = arvot[y][0];
kokoM1 = 0;
for (int koko = 2; y - koko >= -1 && koko <= m; koko++)
{
kokoM1++;
huipunXkorjaus = (koko - 1 + (y & 1)) >> 1; // optimoi
if (y - koko >= 0)
{
int oikeaX = koko == 2 ? 0 : (koko - 2 + (y & 1)) >> 1;
alkuarvo += summatAlas[y][kokoM1] - summatAlas[y - koko][oikeaX];
}
else
alkuarvo += summatAlas[y][kokoM1];
nykyinenArvo = alkuarvo;
//cout << nykyinenArvo << "\n";
if (nykyinenArvo < minimi)
{
minimi = nykyinenArvo;
}
raja = m - koko;
for (int x = 1; x <= raja; x++)
{
nykyinenArvo += summatAlas[y][kokoM1 + x];
if (y - koko >= 0)
{
nykyinenArvo -= summatAlas[y - koko][huipunXkorjaus + x - ((y + koko) & 1)];
}
nykyinenArvo -= summatYlos[y - kokoM1][huipunXkorjaus + x - 1];
if (y < n - 1 && (x > 1 || (y & 1)))
{
nykyinenArvo += summatYlos[y + 1][x - 1 - ((y + 1) & 1)];
}
//cout << nykyinenArvo << "\n";
if (nykyinenArvo < minimi)
{
minimi = nykyinenArvo;
}
}
}
}
cout << arvoYhteensa - minimi;
}

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