CSES - Datatähti 2024 qualification mirror - Results
Submission details
Task:Uolevin kalansaalis
Sender:martinm17
Submission time:2023-11-03 10:58:52 +0200
Language:C++ (C++20)
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.00 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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int triangleScan(vector<vector<int>> &grid, vector<vector<int>> &dp, int size, int n, int m)
{
// cout << "///// size is " << size << endl;
int minTriangle = 1000000;
for (int i = 0; i < n - size + 1; i++)
{
for (int j = 0; j < m - size + 1; j++)
{
// cout << "looking at node " << i << " " << j << endl;
int line = i;
int column = j;
int current_min = 0;
int right_border = column + size - 1;
int left_border = column;
for (int k = line; k < line + size; k++)
{
// cout << "start " << left_border << " end " << right_border << endl;
if (left_border > 0)
{
// cout << "line is " << k << " left border is " << left_border << " right border is " << right_border << endl;
// cout << "**** sum is " << dp[k][right_border] << " - " << dp[k][left_border - 1] << " = " << dp[k][right_border] - dp[k][left_border - 1] << endl;
current_min += dp[k][right_border] - dp[k][left_border - 1];
}
else
{
// cout << "**** sum is " << dp[k][right_border] << endl;
current_min += dp[k][right_border];
}
if (k % 2 == 1)
left_border++;
else
right_border--;
// cout << current_min << endl;
}
// cout << "current min is " << current_min << endl;
minTriangle = min(minTriangle, current_min);
}
// cout << endl;
}
for (int i = n - 1; i >= size - 1; i--)
{
for (int j = 0; j <= m - size; j++)
{
// cout << "looking at node " << i << " " << j << endl;
int line = i;
int column = j;
int current_min = 0;
int right_border = column + size - 1;
int left_border = column;
// cout << "right border is " << right_border << " left border is " << left_border << "line is " << line << endl;
for (int k = size; k > 0; k--)
{
// cout << "start " << left_border << " end " << right_border << endl;
if (left_border > 0)
{
// cout << "line is " << line - size + k << " left border is " << left_border << " right border is " << right_border << endl;
// cout << "**** sum is " << dp[line - size + k][right_border] << " - " << dp[line - size + k][left_border - 1] << " = " << dp[line - size + k][right_border] - dp[line - size + k][left_border - 1] << endl;
current_min += dp[line - size + k][right_border] - dp[line - size + k][left_border - 1];
}
else
{
// cout << "**** sum is " << dp[line - size + k][right_border] << endl;
current_min += dp[line - size + k][right_border];
}
if ((line - size + k) % 2 == 1)
left_border++;
else
right_border--;
// cout << current_min << endl;
}
// cout << "current min is " << current_min << endl;
minTriangle = min(minTriangle, current_min);
}
// cout << endl;
}
return minTriangle;
}
int main()
{
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> adj(n, vector<int>(m, 0));
int total_points = 0;
for (int i = 0; i < k; i++)
{
int a, b;
char c;
cin >> a >> b >> c;
if (c == 'K')
{
// cout << "shrimp detected" << endl;
adj[a - 1][b - 1] = -10;
total_points -= 10;
}
else if (c == 'H')
{
adj[a - 1][b - 1] = 1;
total_points += 1;
}
}
int size = min(n, m);
vector<vector<int>> dp(n, vector<int>(m, 0));
// scan the graph to caclulate the toatal points from each cell and the beginning of the row
for (int i = 0; i < n; i++)
{
int sum = 0;
for (int j = 0; j < m; j++)
{
sum += adj[i][j];
dp[i][j] = sum;
}
}
// loop to display dp table
// for (int i = 0; i < n; i++)
// {
// for (int j = 0; j < m; j++)
// {
// cout << dp[i][j] << " ";
// }
// cout << endl;
// }
// for a triangle of size "size" use the dp table to calculate the sum of the triangle using substraction
int result = triangleScan(adj, dp, size, n, m);
// cout << "total points is " << total_points << endl;
// cout << "result is " << total_points - result << endl;
for (int i = size - 1; i >= 1; i--)
{
// cout << "in for loop " << i << endl;
int current = triangleScan(adj, dp, i, n, m);
// if (current >= result)
// {
// break;
// }
result = min(current, result);
}
cout << total_points - result << endl;
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)