— Dark mode

Datatähti 2024 alku

Uolevin kalansaalis

  • Start: 2023-10-30 00:00:00
  • End: 2023-11-13 00:00:00
CSES - Datatähti 2024 alku - Results
Submission details
Task:Uolevin kalansaalis
Sender:Tipu
Submission time:2023-11-04 22:09:04 +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
#50.00 s1, 2details
#60.00 s1, 2details
#70.00 s1, 2details
#80.00 s1, 2details
#9ACCEPTED0.00 s1, 2details
#10ACCEPTED0.00 s1, 2details
#11ACCEPTED0.00 s1, 2details
#120.00 s1, 2details
#130.00 s1, 2details
#140.00 s1, 2details
#150.00 s1, 2details
#160.01 s2details
#170.01 s2details
#180.23 s2details
#190.01 s2details
#200.01 s2details
#210.23 s2details
#220.01 s2details
#230.02 s2details
#240.03 s2details

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;


struct Hex {       
  public:            
    int l = 0;   
    int r = 0;
};

const int SIZE = 15;

int n, m, k;
int v[SIZE][SIZE];
int v2[SIZE][SIZE];
Hex d[SIZE][SIZE];

int count_l_colum(int i, int j, int l){
    bool add = (i % 2 == 0);
    return (d[i][j].l - d[i-l][j - int(ceil((l-add)/2.0))].l);
} 

int count_r_colum(int i, int j, int l){
    bool add = (i % 2 == 0);
    return (d[i][j].r - d[i-l][j + int((l+add)/2.0)].r);
} 

int scan(int p){

    for (int i = n; i >= 1; i--) {

        for (int h = i; h > 0; h--)
        {        
            int l = 1;
            int j2 = 1;
            int j1 = 1;
            int s = d[i][1].l - d[i-1][1].l; 
            while (j2 <= m)
            {
                while(l < h){
                    j2++;
                    l = j2-j1 + 1;
                    s += count_l_colum(i, j2, l);
                }           
                if(l == h && j2 <= m){
                    p = min(s, p);
                    // cout << "( " << i << ";" << j1 << ";" << l << ") s:"  << s << " p:" << p << endl; 

                    s -= count_r_colum(i, j1, l);
                    j1++;
                    l = j2-j1 + 1;                    

                }

            }
        }        

      

    }     
    return p;   
}


int main() {
    // freopen("input.txt", "r", stdin);



    cin >> n >> m >> k;

    int a, b;
    char c;
    for (int i = 0; i < k; i++) {
        cin >> a >> b >> c;
        if(c == 'H'){
            v[a][b] = 1;
        }else{
            v[a][b] = -10;
        }
    }
    int os = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            bool add = 0;
            if(i % 2 == 0){
                add = 1;
            }
            os += v[i][j];
            d[i][j].l = v[i][j] + d[i-1][j-1+add].l;
            d[i][j].r = v[i][j] + d[i-1][j+add].r;
        }
    }

    // for (int i = 1; i <= n; i++) {
    //     for (int j = 1; j <= m; j++) {
    //         cout << "(" << d[i][j].l << " ; " << d[i][j].r << ")  " ;
    //     }
    //     cout << "\n";
    // }

    int p = 1e6;
    p = scan(p);

    // cout << p << endl;
    // cout << os << endl;
    // assert(p >= os);
    // cout << "\n\n";
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if(v[i][j] != 0){
                v2[n+1-i][j] = v[i][j];
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            bool add = 0;
            if(i % 2 == 0){
                add = 1;
            }
            d[i][j].l = v2[i][j] + d[i-1][j-1+add].l;
            d[i][j].r = v2[i][j] + d[i-1][j+add].r;
        }
    }
    
    // for (int i = 1; i <= n; i++) {
    //     for (int j = 1; j <= m; j++) {
    //         cout << "(" << d[i][j].l << " ; " << d[i][j].r << ")  " ;
    //     }
    //     cout << "\n";
    // }

    p = min(scan(p), p);

    assert((n <= 7 && m <= 7));
    cout << os - p;

}

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
...
view save

correct output
-16
view save

user output
-16
view save

Test 2

Group: 1, 2

Verdict: ACCEPTED

input
5 6 7
1 5 K
4 6 K
2 4 H
2 5 H
...
view save

correct output
0
view save

user output
0
view save

Test 3

Group: 1, 2

Verdict: ACCEPTED

input
5 6 7
5 5 K
2 6 K
2 4 H
2 5 H
...
view save

correct output
0
view save

user output
0
view save

Test 4

Group: 1, 2

Verdict:

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

correct output
50
view save

user output
(empty)

Error:
code: input/code.cpp:139: int main(): Assertion `(n <= 7 && m <= 7)' failed.

Test 5

Group: 1, 2

Verdict:

input
10 10 52
3 5 H
3 1 H
9 6 H
2 8 H
...
view save

correct output
40
view save

user output
(empty)

Error:
code: input/code.cpp:139: int main(): Assertion `(n <= 7 && m <= 7)' failed.

Test 6

Group: 1, 2

Verdict:

input
10 10 60
6 10 H
2 8 H
5 8 H
8 10 H
...
view save

correct output
-15
view save

user output
(empty)

Error:
code: input/code.cpp:139: int main(): Assertion `(n <= 7 && m <= 7)' failed.

Test 7

Group: 1, 2

Verdict:

input
10 10 60
4 7 H
7 4 H
4 10 H
3 6 H
...
view save

correct output
60
view save

user output
(empty)

Error:
code: input/code.cpp:139: int main(): Assertion `(n <= 7 && m <= 7)' failed.

Test 8

Group: 1, 2

Verdict:

input
10 10 40
9 9 H
5 10 H
5 6 H
4 9 H
...
view save

correct output
2
view save

user output
(empty)

Error:
code: input/code.cpp:139: int main(): Assertion `(n <= 7 && m <= 7)' failed.

Test 9

Group: 1, 2

Verdict: ACCEPTED

input
1 1 0
view save

correct output
0
view save

user output
0
view save

Test 10

Group: 1, 2

Verdict: ACCEPTED

input
1 1 1
1 1 K
view save

correct output
0
view save

user output
0
view save

Test 11

Group: 1, 2

Verdict: ACCEPTED

input
1 1 1
1 1 H
view save

correct output
0
view save

user output
0
view save

Test 12

Group: 1, 2

Verdict:

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

correct output
20
view save

user output
(empty)

Error:
code: input/code.cpp:139: int main(): Assertion `(n <= 7 && m <= 7)' failed.

Test 13

Group: 1, 2

Verdict:

input
5 10 32
5 9 H
2 4 H
2 9 H
2 5 H
...
view save

correct output
28
view save

user output
(empty)

Error:
code: input/code.cpp:139: int main(): Assertion `(n <= 7 && m <= 7)' failed.

Test 14

Group: 1, 2

Verdict:

input
10 10 100
2 9 H
5 4 H
5 9 K
6 1 K
...
view save

correct output
-439
view save

user output
(empty)

Error:
code: input/code.cpp:139: int main(): Assertion `(n <= 7 && m <= 7)' failed.

Test 15

Group: 1, 2

Verdict:

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

correct output
88
view save

user output
(empty)

Error:
code: input/code.cpp:139: int main(): Assertion `(n <= 7 && m <= 7)' failed.

Test 16

Group: 2

Verdict:

input
500 500 125000
125 261 K
84 78 K
11 200 K
481 246 K
...
view save

correct output
-624270
view save

user output
(empty)

Test 17

Group: 2

Verdict:

input
500 500 125100
16 61 H
37 62 H
459 125 H
318 476 H
...
view save

correct output
124020
view save

user output
(empty)

Test 18

Group: 2

Verdict:

input
500 500 249999
22 214 H
356 145 H
341 29 H
393 262 H
...
view save

correct output
249999
view save

user output
(empty)

Error:
code: input/code.cpp:139: int main(): Assertion `(n <= 7 && m <= 7)' failed.

Test 19

Group: 2

Verdict:

input
500 500 32000
30 81 H
315 34 H
78 112 H
367 166 H
...
view save

correct output
10126
view save

user output
0
view save

Test 20

Group: 2

Verdict:

input
500 500 126745
164 390 H
126 331 H
164 126 H
55 92 H
...
view save

correct output
-104692
view save

user output
(empty)

Test 21

Group: 2

Verdict:

input
500 500 71200
106 191 H
314 189 H
482 485 H
344 401 H
...
view save

correct output
-335853
view save

user output
(empty)

Error:
code: input/code.cpp:139: int main(): Assertion `(n <= 7 && m <= 7)' failed.

Test 22

Group: 2

Verdict:

input
500 500 67772
421 277 H
428 470 H
169 142 H
256 345 H
...
view save

correct output
-208567
view save

user output
(empty)

Test 23

Group: 2

Verdict:

input
500 500 27434
366 481 H
38 22 H
126 107 H
135 169 H
...
view save

correct output
-57100
view save

user output
-1000000
view save

Test 24

Group: 2

Verdict:

input
500 500 93982
183 13 H
463 230 H
264 351 H
399 290 H
...
view save

correct output
-52800
view save

user output
0
view save

Tasks

A Lumimyrsky-B Monistus-C Laskettelukeskus-D Uolevin kalansaalis-E Käännöt-F Säähavainnot-

Submissions (Tipu)

2023-11-14 12:20:52 372023-11-14 12:20:11 2023-11-14 12:18:22 02023-11-14 12:14:49 372023-11-14 12:13:23 372023-11-14 12:13:04 2023-11-14 12:11:25 372023-11-14 12:09:44 02023-11-14 12:08:15 372023-11-13 00:36:29 372023-11-13 00:33:45 372023-11-13 00:32:11 02023-11-13 00:31:31 02023-11-13 00:00:10 02023-11-12 23:59:14 372023-11-12 23:59:01 372023-11-12 23:58:41 372023-11-12 23:58:08 372023-11-12 23:57:56 02023-11-12 23:57:44 02023-11-12 23:57:30 02023-11-12 23:57:19 02023-11-12 23:57:02 372023-11-12 23:56:05 372023-11-12 23:51:34 372023-11-12 23:49:56 372023-11-12 23:32:32 372023-11-12 23:31:50 372023-11-12 23:31:34 372023-11-12 23:31:16 2023-11-12 23:30:59 2023-11-12 23:29:47 02023-11-12 23:29:08 02023-11-12 23:28:55 372023-11-12 23:28:36 372023-11-12 23:28:21 372023-11-12 23:27:32 02023-11-12 23:26:47 02023-11-12 23:26:31 02023-11-12 23:26:23 02023-11-12 23:26:12 2023-11-12 23:24:20 02023-11-12 23:23:57 372023-11-12 23:23:44 02023-11-12 23:23:27 02023-11-12 22:45:08 02023-11-12 22:43:28 02023-11-12 22:43:02 372023-11-12 22:16:25 372023-11-12 22:13:15 372023-11-12 22:12:52 02023-11-12 22:12:28 02023-11-12 22:11:58 372023-11-12 22:09:00 372023-11-12 22:07:22 372023-11-12 22:07:10 02023-11-12 21:47:39 02023-11-12 21:36:51 02023-11-12 21:35:12 372023-11-12 21:23:07 372023-11-12 21:22:42 2023-11-12 21:00:26 372023-11-12 20:59:17 372023-11-12 20:57:09 372023-11-12 20:55:32 372023-11-12 20:55:08 372023-11-12 20:54:55 372023-11-12 20:54:36 372023-11-12 20:54:18 372023-11-12 20:54:06 372023-11-12 20:53:55 372023-11-12 20:53:41 372023-11-12 20:53:28 372023-11-12 20:53:13 372023-11-12 20:52:54 372023-11-12 20:52:17 372023-11-12 20:52:02 372023-11-12 20:51:47 372023-11-12 20:51:32 372023-11-12 20:51:15 372023-11-12 20:50:57 372023-11-12 20:48:46 372023-11-12 20:45:05 372023-11-12 20:44:20 372023-11-12 20:43:56 2023-11-12 20:43:33 372023-11-12 20:43:14 2023-11-12 20:42:50 372023-11-12 20:42:19 372023-11-12 20:19:47 02023-11-12 20:06:18 02023-11-12 20:05:01 02023-11-12 20:04:42 02023-11-12 19:53:06 372023-11-12 19:52:49 02023-11-12 19:39:33 02023-11-05 18:12:04 372023-11-05 18:09:30 02023-11-05 17:29:44 02023-11-04 22:13:17 02023-11-04 22:09:25 02023-11-04 22:09:04 02023-11-04 22:08:21 02023-11-04 22:08:08 02023-11-04 22:07:44 02023-11-04 22:07:24 02023-11-04 22:07:15 02023-11-04 22:07:00 02023-11-04 22:06:45 02023-11-04 22:06:24 02023-11-04 21:23:30 02023-11-04 21:23:05 02023-11-04 21:22:50 02023-11-04 21:19:31 02023-11-04 21:19:13 02023-11-04 21:18:53 02023-11-04 21:12:55 02023-11-04 21:03:14 02023-11-04 18:18:32 02023-11-04 18:18:00 02023-11-04 18:16:37 02023-11-04 18:16:15 02023-11-04 18:15:52 02023-11-04 18:14:24 2023-11-04 18:13:05 2023-11-04 18:05:21 02023-11-04 17:32:36 02023-11-04 17:19:11 02023-10-30 23:57:14 0