CSES - Datatähti 2024 alku - Results
Submission details
Task:Uolevin kalansaalis
Sender:Mariia
Submission time:2023-11-11 18:34:28 +0200
Language:C++ (C++11)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 2details
#2ACCEPTED0.00 s1, 2details
#3ACCEPTED0.00 s1, 2details
#40.00 s1, 2details
#5ACCEPTED0.00 s1, 2details
#6ACCEPTED0.00 s1, 2details
#7ACCEPTED0.00 s1, 2details
#8ACCEPTED0.00 s1, 2details
#90.00 s1, 2details
#100.00 s1, 2details
#110.00 s1, 2details
#120.00 s1, 2details
#13ACCEPTED0.00 s1, 2details
#14ACCEPTED0.00 s1, 2details
#150.00 s1, 2details
#160.38 s2details
#170.38 s2details
#180.38 s2details
#190.38 s2details
#200.38 s2details
#210.38 s2details
#220.38 s2details
#230.39 s2details
#240.38 s2details

Code

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    vector<vector<vector<int>>> dp1(min(n, m) + 1, vector<vector<int>>(n, vector<int>(m)));
    vector<vector<vector<int>>> dp2(min(n, m) + 1, vector<vector<int>>(n, vector<int>(m)));

    vector<vector<int>> t(n, vector<int> (m, 0));
    int SUM = 0;
    for (int i = 0; i < k; i++) {
        int x, y; char type;
        cin >> y >> x >> type;
        y--; x--;
        if (type == 'H') {
            t[y][x] = 1;
        } else {
            t[y][x] = -10;
        }
        SUM += t[y][x];
    }

    for (int y = 0; y < n; y++) {
        for (int x = 0; x < m; x++) {
            dp1[1][y][x] = t[y][x];
            dp2[1][y][x] = t[y][x];
        }
    }

    vector<vector<int>> pr(n, vector<int> (m, 0));
    for (int j = 0; j < n; j++) {
        pr[j][0] = t[j][0];
        for (int i = 1; i < m; i++) {
            pr[j][i] = pr[j][i - 1] + t[j][i];
        }
    }

    int mini = 1e9;

    for (int s = 2; s <= min(n, m); s++) {
        for (int y = 0; y + s - 1 < n; y++) {
            for (int x = 0; x + s - 1 < m; x++) {
                if (y + 1 >= n) {
                    dp1[s][y][x] = 1e9;
                    continue;
                }
                if (x + y % 2 >= m) {
                    dp1[s][y][x] = 1e9;
                    continue;
                }
                if (dp1[s - 1][y + 1][x + y % 2] == 1e9) {
                    dp1[s][y][x] = 1e9;
                    continue;
                }
                int sum = 0;
                if (x == 0) {
                    sum = pr[y][x + s - 1];
                } else {
                    sum = pr[y][x + s - 1] - pr[y][x - 1];
                }
                dp1[s][y][x] = dp1[s - 1][y + 1][x + y % 2] + sum;

                //cout << dp1[s][y][x] << '\n';
                if (dp1[s][y][x] < mini) {
                    mini = dp1[s][y][x];
                }
            }
        }
    }

    for (int s = 2; s <= min(n, m); s++) {
        for (int y = n - 1; y - s + 1 >= 0; y--) {
            for (int x = 0; x + s - 1 < m; x++) {
                if (y - 1 < 0) {
                    dp1[s][y][x] = 1e9;
                    continue;
                }
                if (x + y % 2 >= m) {
                    dp1[s][y][x] = 1e9;
                    continue;
                }
                if (dp1[s - 1][y - 1][x + y % 2] == 1e9) {
                    dp1[s][y][x] = 1e9;
                    continue;
                }
                int sum = 0;
                if (x == 0) {
                    sum = pr[y][x + s - 1];
                } else {
                    sum = pr[y][x + s - 1] - pr[y][x - 1];
                }
                dp2[s][y][x] = dp2[s - 1][y - 1][x + y % 2] + sum;

                //cout << dp2[s][y][x] << '\n';
                if (dp2[s][y][x] < mini) {
                    mini = dp2[s][y][x];
                }
            }
        }
    }

    cout << SUM - mini;
}

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:

input
10 10 51
3 3 H
6 3 H
9 5 H
5 10 H
...

correct output
50

user output
49

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:

input
1 1 0

correct output
0

user output
-1000000000

Test 10

Group: 1, 2

Verdict:

input
1 1 1
1 1 K

correct output
0

user output
-1000000010

Test 11

Group: 1, 2

Verdict:

input
1 1 1
1 1 H

correct output
0

user output
-999999999

Test 12

Group: 1, 2

Verdict:

input
10 5 32
10 3 H
4 4 H
3 3 H
5 4 H
...

correct output
20

user output
19

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:

input
10 10 100
8 9 H
5 10 H
5 4 H
3 9 H
...

correct output
88

user output
86

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)