CSES - Datatähti 2024 alku - Results
Submission details
Task:Uolevin kalansaalis
Sender:kasvoton
Submission time:2023-11-10 18:09:45 +0200
Language:C++ (C++11)
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
#18ACCEPTED0.13 s2details
#19--2details
#20--2details
#21--2details
#22--2details
#23--2details
#24--2details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:79:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for (int i = 0; i < q.size(); i++) g(q[i]);
      |                         ~~^~~~~~~~~~

Code

#include <iostream>
#include <array>
#include <vector>
using namespace std;
int s[500][501];
int o[501];
int p;
int f(array<int, 4> a);
void g(array <int, 4> a);
int main() {
int n, m, k;
cin >> n >> m >> k;
if (!k) {
cout << "0\n";
return 0;
}
int a[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) a[i][j] = 0;
}
int b = 0;
for (int i = 0; i < k; i++) {
int y, x;
char z;
cin >> y >> x >> z;
if (z == 'H') {
a[y-1][x-1] = 1;
b++;
}
else {
a[y-1][x-1] = -10;
b -= 10;
}
}
if (b == n * m) {
cout << b - 1 << "\n";
return 0;
}
if (b == k) {
cout << b << "\n";
return 0;
}
for (int i = 0; i < n; i++) {
s[i][0] = 0;
for (int j = 1; j < m+1; j++) s[i][j] = s[i][j-1] + a[i][j-1];
}
int t;
if (n <= m) t = n;
else t = m;
vector<array<int, 4>> q;
for (int i = t-1; i > 1; i--) {
int x;
if ((n-i)&1) x = m - i;
else x = 0;
q.emplace_back((array<int, 4>){n-i, x, 1, i});
if ((i-1)&1) x = m - i;
else x = 0;
q.emplace_back((array<int, 4>){i-1, x, 0, i});
}
for (int i = 0; i < n-t+1; i++) {
for (int j = 0; j < m-t+1; j++) {
q.emplace_back((array<int, 4>){i, j, 1, t});
q.emplace_back((array<int, 4>){n-i-1, j, 0, t});
}
}
p = -10;
o[0] = 0;
for (int i = 1; i <= t; i++) o[i] = o[i-1] + i * (-10);
for (int i = 0; i < q.size(); i++) g(q[i]);
cout << b - p << "\n";
return 0;
}
int f(array<int, 4> a) {
int v = 0, z = a[1];
if (a[2]) {
for (int i = a[0], w = a[3]; w > 0; i++, w--, z = a[1]+(i-a[0]+(a[0]&1))/2)
v += s[i][z+w] - s[i][z];
}
else {
for (int i = a[0], w = a[3]; w > 0; i--, w--, z = a[1]+(a[0]-i+(a[0]&1))/2)
v += s[i][z+w] - s[i][z];
}
return v;
}
void g(array <int, 4> a) {
if (p <= o[a[3]]) return;
int v = f(a);
if (v == 0) return;
if (v < p) p = v;
a[3]--;
g(a);
a[1]++;
g(a);
if (a[2]) a[0]++;
else a[0]--;
a[1] -= (a[0] & 1);
g(a);
return;
}

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: 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:

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)