CSES - Datatähti 2021 loppu - Results
Submission details
Task:Koodarit
Sender:xnor
Submission time:2021-01-23 19:14:02 +0200
Language:Rust
Status:READY
Result:34
Feedback
groupverdictscore
#1ACCEPTED34
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.01 s1, 2, 3details
#3ACCEPTED0.01 s1, 2, 3details
#4ACCEPTED0.01 s1, 2, 3details
#5ACCEPTED0.01 s1, 2, 3details
#6ACCEPTED0.01 s1, 2, 3details
#7ACCEPTED0.01 s1, 2, 3details
#8ACCEPTED0.01 s1, 2, 3details
#9ACCEPTED0.01 s1, 2, 3details
#10ACCEPTED0.01 s1, 2, 3details
#11ACCEPTED0.01 s1, 2, 3details
#12ACCEPTED0.01 s1, 3details
#13ACCEPTED0.01 s1, 3details
#14ACCEPTED0.01 s1, 3details
#15ACCEPTED0.02 s1, 3details
#16ACCEPTED0.02 s1, 3details
#17ACCEPTED0.52 s2, 3details
#18--2, 3details
#19--2, 3details
#20--2, 3details
#21--2, 3details
#22--2, 3details
#23--2, 3details
#24--3details
#25--3details
#26--3details
#27--3details
#28--3details
#29--3details
#30--3details
#31--3details

Code

use std::io::{self, BufRead};

fn main() {
    let mut lines = io::BufReader::new(io::stdin()).lines();

    let line1 = lines.next().unwrap().unwrap();
    let line2 = lines.next().unwrap().unwrap();

    let l1: Vec<&str> = line1.split_ascii_whitespace().collect();
    let l2: Vec<&str> = line2.split_ascii_whitespace().collect();

    let n = l1[0].parse::<usize>().unwrap();
    let mut k = l1[1].parse::<usize>().unwrap();

    let mut xs = Vec::new();

    for i in 0..n {
        xs.push(l2[i].parse::<usize>().unwrap());
    }

    xs.sort();

    let mut i = 0;
    while i < xs.len() - 1 {
        if xs[i] == xs[i + 1] {
            k -= 1;
            if k == 0 {
                println!("0");
                return;
            }
            xs.remove(i);
            xs.remove(i);
            continue;
        }

        i += 1;
    }

    let mut chunks = Vec::new();
    for i in 0..xs.len() / 2 {
        let f = xs[2 * i];
        let l = xs[2 * i + 1];
        chunks.push(Chunk {
            len: 2,
            first: f,
            last: l,
            all: vec![0, l - f],
            no_first: vec![0],
            no_last: vec![0],
            no_firstlast: vec![0],
        });
    }
    if xs.len() % 2 == 1 {
        chunks.push(Chunk {
            len: 1,
            first: xs[xs.len() - 1],
            last: xs[xs.len() - 1],
            all: vec![0],
            no_first: vec![0],
            no_last: vec![0],
            no_firstlast: vec![0],
        });
    }

    loop {
        if chunks.len() == 1 {
            break;
        }

        let mut new_chunks = Vec::new();

        for k in 0..chunks.len() / 2 {
            let c1 = &chunks[2 * k];
            let c2 = &chunks[2 * k + 1];

            let mut c3 = Chunk {
                len: c1.len + c2.len,
                first: c1.first,
                last: c2.last,
                all: vec![0],
                no_first: vec![0],
                no_last: vec![0],
                no_firstlast: vec![0],
            };

            for m in 1..=c3.len / 2 {
                let mut cost = usize::MAX;
                for j in m + 1 - c1.all.len().min(m+1)..c2.all.len().min(m + 1) {
                    let nc = c1.all[m - j] + c2.all[j];
                    if nc < cost {
                        cost = nc;
                    }
                }
                for j in m - c1.no_last.len().min(m)..c2.no_first.len().min(m) {
                    let nc = c1.no_last[m - 1 - j] + c2.no_first[j] + c2.first - c1.last;
                    if nc < cost {
                        cost = nc;
                    }
                }
                c3.all.push(cost);
            }

            for m in 1..=(c3.len - 1) / 2 {
                let mut cost = usize::MAX;
                for j in m + 1 - c1.no_first.len().min(m+1)..c2.all.len().min(m + 1) {
                    let nc = c1.no_first[m - j] + c2.all[j];
                    if nc < cost {
                        cost = nc;
                    }
                }
                for j in m - c1.no_firstlast.len().min(m)..c2.no_first.len().min(m) {
                    let nc = c1.no_firstlast[m - 1 - j] + c2.no_first[j] + c2.first - c1.last;
                    if nc < cost {
                        cost = nc;
                    }
                }
                c3.no_first.push(cost);
            }

            for m in 1..=(c3.len - 1) / 2 {
                let mut cost = usize::MAX;
                for j in m + 1 - c1.all.len().min(m+1)..c2.no_last.len().min(m + 1) {
                    let nc = c1.all[m - j] + c2.no_last[j];
                    if nc < cost {
                        cost = nc;
                    }
                }
                for j in m - c1.no_last.len().min(m)..c2.no_firstlast.len().min(m) {
                    let nc = c1.no_last[m - 1 - j] + c2.no_firstlast[j] + c2.first - c1.last;
                    if nc < cost {
                        cost = nc;
                    }
                }
                c3.no_last.push(cost);
            }

            for m in 1..=(c3.len - 2) / 2 {
                let mut cost = usize::MAX;
                for j in m + 1 - c1.no_first.len().min(m+1)..c2.no_last.len().min(m + 1) {
                    let nc = c1.no_first[m - j] + c2.no_last[j];
                    if nc < cost {
                        cost = nc;
                    }
                }
                for j in m - c1.no_firstlast.len().min(m)..c2.no_firstlast.len().min(m) {
                    let nc = c1.no_firstlast[m - 1 - j] + c2.no_firstlast[j] + c2.first - c1.last;
                    if nc < cost {
                        cost = nc;
                    }
                }
                c3.no_firstlast.push(cost);
            }

            new_chunks.push(c3);
        }

        if chunks.len() % 2 == 1 {
            new_chunks.push(chunks.last().unwrap().clone());
        }

        chunks = new_chunks;
    }

    println!("{}", chunks[0].all[k]);
}

#[derive(Clone, Debug)]
struct Chunk {
    len: usize,
    first: usize,
    last: usize,
    all: Vec<usize>,
    no_first: Vec<usize>,
    no_last: Vec<usize>,
    no_firstlast: Vec<usize>,
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
8 3
3 1 2 7 9 3 4 7

correct output
1

user output
1

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
2 1
2 13

correct output
11

user output
11

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
20 10
16 20 6 15 19 12 11 17 20 6 15...

correct output
6

user output
6

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
14 5
11 3 8 3 14 8 10 13 11 10 17 1...

correct output
0

user output
0

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
15 1
8 5 1 8 18 15 6 20 14 9 10 9 1...

correct output
0

user output
0

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
10 3
10 19 16 15 12 5 14 8 3 15

correct output
4

user output
4

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
202 90
177 187 183 647 616 580 499 78...

correct output
213

user output
213

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

input
2000 512
141 583 135 833 900 308 248 58...

correct output
0

user output
0

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

input
2000 972
685 4 289 865 93 159 48 866 56...

correct output
276

user output
276

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

input
2000 1000
698 153 298 118 631 341 238 7 ...

correct output
517

user output
517

Test 11

Group: 1, 2, 3

Verdict: ACCEPTED

input
2000 1
983 144 449 584 839 166 77 885...

correct output
0

user output
0

Test 12

Group: 1, 3

Verdict: ACCEPTED

input
1464 320
846762124 954854396 12767390 7...

correct output
35809369

user output
35809369

Test 13

Group: 1, 3

Verdict: ACCEPTED

input
2000 231
801945178 924940258 369188694 ...

correct output
7831421

user output
7831421

Test 14

Group: 1, 3

Verdict: ACCEPTED

input
2000 461
464790475 932031556 838378103 ...

correct output
37272564

user output
37272564

Test 15

Group: 1, 3

Verdict: ACCEPTED

input
2000 100
484046702 267135814 995006323 ...

correct output
1268400

user output
1268400

Test 16

Group: 1, 3

Verdict: ACCEPTED

input
2000 996
98352148 438929491 242618159 1...

correct output
445965905

user output
445965905

Test 17

Group: 2, 3

Verdict: ACCEPTED

input
65879 19675
896 316 972 476 636 227 716 78...

correct output
0

user output
0

Test 18

Group: 2, 3

Verdict:

input
200000 53820
995 720 135 767 943 742 191 26...

correct output
0

user output
(empty)

Test 19

Group: 2, 3

Verdict:

input
200000 32297
527 947 84 851 908 833 339 112...

correct output
0

user output
(empty)

Test 20

Group: 2, 3

Verdict:

input
200000 99982
561 174 242 275 460 109 664 68...

correct output
322

user output
(empty)

Test 21

Group: 2, 3

Verdict:

input
200000 99955
911 33 314 861 298 117 972 982...

correct output
245

user output
(empty)

Test 22

Group: 2, 3

Verdict:

input
200000 99972
783 1000 673 611 87 452 702 92...

correct output
290

user output
(empty)

Test 23

Group: 2, 3

Verdict:

input
200000 99961
795 136 128 643 60 422 371 839...

correct output
252

user output
(empty)

Test 24

Group: 3

Verdict:

input
195426 76599
442872072 619088799 118541378 ...

correct output
143376538

user output
(empty)

Test 25

Group: 3

Verdict:

input
200000 1661
894106972 620084612 931442312 ...

correct output
33089

user output
(empty)

Test 26

Group: 3

Verdict:

input
200000 86032
211444153 846442677 297198384 ...

correct output
196001810

user output
(empty)

Test 27

Group: 3

Verdict:

input
200000 28275
28280312 349705372 96535649 84...

correct output
11627219

user output
(empty)

Test 28

Group: 3

Verdict:

input
200000 81473
178022892 112774306 250584651 ...

correct output
162430841

user output
(empty)

Test 29

Group: 3

Verdict:

input
200000 99987
297598052 494409138 182268523 ...

correct output
489497036

user output
(empty)

Test 30

Group: 3

Verdict:

input
200000 99971
316462272 843156468 434342923 ...

correct output
483167476

user output
(empty)

Test 31

Group: 3

Verdict:

input
200000 99964
811543559 465033274 620180191 ...

correct output
481497328

user output
(empty)