CSES - Datatähti 2022 loppu - Results
Submission details
Task:Peli
Sender:xnor
Submission time:2022-01-22 18:50:00 +0200
Language:Rust
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.01 s1, 2, 3details
#20.01 s2, 3details
#30.01 s3details
#4ACCEPTED0.01 s1, 2, 3details
#5ACCEPTED0.01 s1, 2, 3details

Code

use std::io::{stdin, BufRead, BufReader};

fn main() {
    let mut stdin = BufReader::new(stdin());
    let mut cur_line = String::new();

    stdin.read_line(&mut cur_line).unwrap();
    let mut nums = cur_line
        .split_whitespace()
        .map(|s| s.parse::<usize>().unwrap());

    let n = nums.next().unwrap();
    let k = nums.next().unwrap();

    cur_line.clear();
    stdin.read_line(&mut cur_line).unwrap();

    let v = cur_line.trim().as_bytes();

    let mut dp = vec![[[[0u16; 50]; 50]; 50]; n];

    for a in 0..k {
        for b in 0..k {
            for c in 0..k {
                if a + b + c < k {
                    match v.last().unwrap() {
                        b'A' => {
                            if a == 0 && b > 0 && c > 0 {
                                dp[v.len() - 1][a][b][c] = 1;
                            }
                        }
                        b'B' => {
                            if a > 0 && b == 0 && c > 0 {
                                dp[v.len() - 1][a][b][c] = 1;
                            }
                        }
                        b'C' => {
                            if a > 0 && b > 0 && c == 0 {
                                dp[v.len() - 1][a][b][c] = 1;
                            }
                        }
                        _ => (),
                    }
                }
            }
        }
    }

    for i in (0..n - 1).rev() {
        for a in 0..k {
            for b in 0..k {
                if a + b >= k {
                    break;
                }
                for c in 0..k {
                    if a + b + c >= k {
                        break;
                    }
                    match v[i] {
                        b'A' => {
                            if a == 0 && b > 0 && c > 0 {
                                dp[i][a][b][c] = 1 + dp[i + 1][a][b - 1][c - 1];
                            } else if a < k - 1 {
                                dp[i][a][b][c] = dp[i + 1][a + 1][b][c].max(dp[i + 1][a][b][c]);
                            }
                        }
                        b'B' => {
                            if a > 0 && b == 0 && c > 0 {
                                dp[i][a][b][c] = 1 + dp[i + 1][a - 1][b][c - 1];
                            } else if b < k - 1 {
                                dp[i][a][b][c] = dp[i + 1][a][b + 1][c].max(dp[i + 1][a][b][c]);
                            }
                        }
                        b'C' => {
                            if a > 0 && b > 0 && c == 0 {
                                dp[i][a][b][c] = 1 + dp[i + 1][a - 1][b - 1][c];
                            } else if c < k - 1 {
                                dp[i][a][b][c] = dp[i + 1][a][b][c + 1].max(dp[i + 1][a][b][c]);
                            }
                        }
                        _ => (),
                    }
                }
            }
        }
    }

    println!("{}", dp[0][0][0][0]);
}

Test details

Test 1

Group: 1, 2, 3

Verdict:

input
100000 3
BBAACBCBACBACABBCBAABCBCCBCCAA...

correct output
18201

user output
(empty)

Error:
memory allocation of 25000000000 bytes failed

Test 2

Group: 2, 3

Verdict:

input
100000 10
BAACABCCBCBAACBBCCCCABBBBACCBA...

correct output
29684

user output
(empty)

Error:
memory allocation of 25000000000 bytes failed

Test 3

Group: 3

Verdict:

input
100000 50
ACAABCBBAAAACCBBABACACACBCAACA...

correct output
32740

user output
(empty)

Error:
memory allocation of 25000000000 bytes failed

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
3 1
ABC

correct output
0

user output
0

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
3 2
ABC

correct output
0

user output
0