Submission details
Task:Keke's delivery service
Sender:aalto26jw_004
Submission time:2026-11-11 17:48:19 +0200
Language:Rust (2021)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails
#7ACCEPTED0.00 sdetails
#8ACCEPTED0.00 sdetails
#9ACCEPTED0.00 sdetails
#10ACCEPTED0.00 sdetails
#11ACCEPTED0.00 sdetails
#12ACCEPTED0.00 sdetails
#13ACCEPTED0.00 sdetails
#14ACCEPTED0.00 sdetails
#15ACCEPTED0.00 sdetails
#16ACCEPTED0.00 sdetails
#17ACCEPTED0.00 sdetails
#18ACCEPTED0.00 sdetails
#19ACCEPTED0.00 sdetails
#20ACCEPTED0.00 sdetails
#21ACCEPTED0.00 sdetails
#22ACCEPTED0.00 sdetails
#23ACCEPTED0.00 sdetails
#24ACCEPTED0.00 sdetails
#25ACCEPTED0.00 sdetails
#26ACCEPTED0.00 sdetails
#27ACCEPTED0.00 sdetails
#28ACCEPTED0.00 sdetails
#29ACCEPTED0.00 sdetails
#30ACCEPTED0.00 sdetails
#31ACCEPTED0.00 sdetails
#32ACCEPTED0.00 sdetails
#33ACCEPTED0.00 sdetails
#34ACCEPTED0.00 sdetails
#35ACCEPTED0.00 sdetails
#36ACCEPTED0.00 sdetails
#37ACCEPTED0.00 sdetails
#38ACCEPTED0.01 sdetails
#39ACCEPTED0.01 sdetails
#40ACCEPTED0.01 sdetails
#41ACCEPTED0.01 sdetails
#42ACCEPTED0.01 sdetails
#43ACCEPTED0.01 sdetails
#44ACCEPTED0.01 sdetails
#45ACCEPTED0.01 sdetails
#46ACCEPTED0.01 sdetails
#47ACCEPTED0.01 sdetails
#48ACCEPTED0.02 sdetails
#49ACCEPTED0.02 sdetails
#50ACCEPTED0.02 sdetails
#51ACCEPTED0.02 sdetails
#52ACCEPTED0.02 sdetails
#53ACCEPTED0.06 sdetails
#54ACCEPTED0.06 sdetails
#55ACCEPTED0.06 sdetails
#56ACCEPTED0.06 sdetails
#57ACCEPTED0.06 sdetails
#58ACCEPTED0.06 sdetails
#59ACCEPTED0.06 sdetails
#60ACCEPTED0.06 sdetails
#61ACCEPTED0.06 sdetails
#62ACCEPTED0.06 sdetails

Code

#![allow(unused)]

use std::collections::*;
use std::io;

fn take_int() -> usize {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    return input.trim().parse::<usize>().unwrap();
}

fn take_tuple() -> (i64, i64, i64, i64) {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let mut it = input.trim().split_whitespace().map(|x| x.parse::<i64>().unwrap());
    (it.next().unwrap(), it.next().unwrap(),it.next().unwrap(), it.next().unwrap())
}

fn dist(a: (i64, i64), b: (i64, i64)) -> f64 {
    ((a.0 - b.0) as f64).hypot((a.1 - b.1) as f64)
}

fn main() {
    let mut s = String::new();
    let mut n = take_int();
    let mut pts: Vec<(i64, i64)> = Vec::with_capacity(2 * n);
    for _ in 0..n {
        let (a, b, c, d) = take_tuple();
        pts.push((a, b));
        pts.push((c, d));
    }
    let m = 2 * n;

    let home: Vec<f64> = pts.iter().map(|&p| dist(p, (0, 0))).collect();
    let d: Vec<Vec<f64>> = pts
        .iter()
        .map(|&p| pts.iter().map(|&q| dist(p, q)).collect())
        .collect();

    let mut pow3 = vec![1usize; n + 1];
    for i in 1..=n {
        pow3[i] = pow3[i - 1] * 3;
    }
    let total = pow3[n];
    let mut dp = vec![f64::INFINITY; total * m];

    for i in 0..n {
        dp[pow3[i] * m + 2 * i] = home[2 * i];
    }

    let mut digits = vec![0usize; n];
    for st in 0..total {
        let mut t = st;
        for i in 0..n {
            digits[i] = t % 3;
            t /= 3;
        }
        for p in 0..m {
            let cur = dp[st * m + p];
            if cur == f64::INFINITY {
                continue;
            }
            for i in 0..n {
                let target = match digits[i] {
                    0 => 2 * i,
                    1 => 2 * i + 1,
                    _ => continue,
                };
                let ns = st + pow3[i];
                let v = cur + d[p][target];
                let slot = &mut dp[ns * m + target];
                if v < *slot {
                    *slot = v;
                }
            }
        }
    }

    let full = total - 1;
    let ans = (0..m)
        .map(|p| dp[full * m + p] + home[p])
        .fold(f64::INFINITY, f64::min);

    println!("{}", ans);
}

Test details

Test 1

Verdict: ACCEPTED

input
1
1 2 5 7 

correct output
17.24151748197526515596

user output
17.241517481975265

Test 2

Verdict: ACCEPTED

input
1
-2 10 5 9 

correct output
27.56473698003804521928

user output
27.564736980038045

Test 3

Verdict: ACCEPTED

input
2
-1 -7 -10 9 
1 9 -1 0 

correct output
46.64817201984418185146

user output
46.64817201984418

Test 4

Verdict: ACCEPTED

input
2
1 -9 4 7 
-4 -8 0 1 

correct output
38.53321457061962859031

user output
38.53321457061963

Test 5

Verdict: ACCEPTED

input
2
6 2 -6 8 
7 8 10 -7 

correct output
58.49347834429028263753

user output
58.49347834429028

Test 6

Verdict: ACCEPTED

input
2
6 2 -6 8 
7 8 10 -7 

correct output
58.49347834429028263753

user output
58.49347834429028

Test 7

Verdict: ACCEPTED

input
3
10 8 1 -7 
10 7 5 2 
4 2 -6 -8 

correct output
47.94841075476520489418

user output
47.948410754765206

Test 8

Verdict: ACCEPTED

input
3
-6 -9 8 7 
-6 -3 9 10 
0 -9 2 -2 

correct output
53.42086935541394488933

user output
53.42086935541394

Test 9

Verdict: ACCEPTED

input
3
8 9 -4 -6 
7 -9 -10 -3 
-8 10 2 -8 

correct output
75.43730966940650396746

user output
75.4373096694065

Test 10

Verdict: ACCEPTED

input
3
8 4 2 -1 
-5 -8 -7 -7 
-2 -7 -8 -5 

correct output
41.03401888405835429979

user output
41.034018884058355

Test 11

Verdict: ACCEPTED

input
3
-4 4 0 -4 
6 1 6 -8 
8 -8 -7 -6 

correct output
51.02746211319720185187

user output
51.0274621131972

Test 12

Verdict: ACCEPTED

input
3
-1 -1 -4 4 
-6 -5 -5 -10 
7 4 -8 0 

correct output
49.16957315214831639866

user output
49.16957315214832

Test 13

Verdict: ACCEPTED

input
3
5 -9 2 5 
9 7 -7 8 
6 -9 -3 9 

correct output
56.01093630215238362152

user output
56.01093630215239

Test 14

Verdict: ACCEPTED

input
4
-9 -6 6 -4 
-1 10 5 -1 
10 -4 1 -5 
0 -9 -9 -2 

correct output
69.46799309053363308958

user output
69.46799309053362

Test 15

Verdict: ACCEPTED

input
4
8 -10 10 -5 
8 -3 1 7 
-6 -2 -10 2 
-1 6 -2 -2 

correct output
62.32599841627421704063

user output
62.325998416274224

Test 16

Verdict: ACCEPTED

input
4
-10 -3 0 0 
0 -10 -8 -4 
-8 -10 -6 8 
-2 -8 -5 -8 

correct output
49.37474628842959419733

user output
49.37474628842959

Test 17

Verdict: ACCEPTED

input
4
9 -10 3 -3 
5 -10 -8 6 
-9 -3 6 8 
-4 5 1 4 

correct output
70.54491148050797239000

user output
70.54491148050798

Test 18

Verdict: ACCEPTED

input
4
3 2 0 9 
1 3 8 5 
4 -6 5 -8 
5 7 -6 10 

correct output
55.77371783018015604511

user output
55.773717830180146

Test 19

Verdict: ACCEPTED

input
4
4 5 0 7 
7 5 -10 4 
6 -6 1 10 
-4 2 -10 0 

correct output
58.25155150420911822143

user output
58.25155150420911

Test 20

Verdict: ACCEPTED

input
4
-7 3 -4 -6 
-9 3 -1 -5 
7 1 9 2 
5 5 6 8 

correct output
51.95472904146592808827

user output
51.954729041465924

Test 21

Verdict: ACCEPTED

input
4
8 3 -7 6 
0 6 9 -8 
-2 8 -9 -9 
9 -6 3 -2 

correct output
71.27875557664922673284

user output
71.27875557664923

Test 22

Verdict: ACCEPTED

input
4
6 -7 1 10 
-8 -6 3 -9 
-9 -7 -4 -9 
-2 5 1 -7 

correct output
64.30357123791869498886

user output
64.3035712379187

Test 23

Verdict: ACCEPTED

input
5
3 9 -3 -6 
3 -2 -7 3 
10 4 -3 2 
10 9 -6 4 
...

correct output
65.29921928785613079865

user output
65.29921928785613

Test 24

Verdict: ACCEPTED

input
5
-4 -10 10 -4 
6 2 10 3 
-6 -3 -8 -6 
9 9 -9 9 
...

correct output
82.23748773331917538004

user output
82.23748773331917

Test 25

Verdict: ACCEPTED

input
5
8 -9 -3 -2 
1 -4 10 5 
5 5 7 -3 
-8 -1 9 -5 
...

correct output
67.56153807887115932823

user output
67.56153807887117

Test 26

Verdict: ACCEPTED

input
5
-5 4 -1 4 
-2 9 -5 -8 
8 5 -7 2 
-10 7 10 8 
...

correct output
86.95689997133690237602

user output
86.95689997133691

Test 27

Verdict: ACCEPTED

input
5
-10 -6 6 -2 
-9 -2 3 -1 
-10 -8 9 5 
-2 -3 -5 -2 
...

correct output
60.24622192778474186192

user output
60.24622192778474

Test 28

Verdict: ACCEPTED

input
5
-1 -1 -4 4 
-6 -5 -5 -10 
7 4 -8 0 
3 2 -5 -5 
...

correct output
56.09845589945781874422

user output
56.09845589945782

Test 29

Verdict: ACCEPTED

input
5
5 -9 2 5 
9 7 -7 8 
6 -9 -3 9 
-7 0 -5 -2 
...

correct output
66.46035926536274213855

user output
66.46035926536274

Test 30

Verdict: ACCEPTED

input
5
9 -8 -1 1 
-6 5 2 -4 
3 8 4 -9 
-8 3 5 3 
...

correct output
68.92236432287188030443

user output
68.92236432287189

Test 31

Verdict: ACCEPTED

input
5
-2 8 8 9 
9 8 4 -2 
3 9 2 1 
-6 -7 -2 -8 
...

correct output
68.57347683433427024124

user output
68.57347683433426

Test 32

Verdict: ACCEPTED

input
5
1 -10 6 7 
7 -3 -8 7 
2 2 1 -2 
-1 -6 -1 4 
...

correct output
67.26306049003909036388

user output
67.26306049003908

Test 33

Verdict: ACCEPTED

input
6
633196515 485923574 -954265220...

correct output
7364359200.7228123750537633895...

user output
7364359200.722812

Test 34

Verdict: ACCEPTED

input
6
-54250287 -57195506 925370083 ...

correct output
6070544873.2142193284817039966...

user output
6070544873.214219

Test 35

Verdict: ACCEPTED

input
6
717786754 -23244255 -670216484...

correct output
6236901804.9330618907697498798...

user output
6236901804.933063

Test 36

Verdict: ACCEPTED

input
6
-747595481 -560868740 20781968...

correct output
6206348638.7408930636011064052...

user output
6206348638.740893

Test 37

Verdict: ACCEPTED

input
6
369551931 -830851741 -63146575...

correct output
7466232851.6345729152671992778...

user output
7466232851.634571

Test 38

Verdict: ACCEPTED

input
7
-503438465 -401188031 -2915208...

correct output
7182008964.6697172718122601509...

user output
7182008964.669717

Test 39

Verdict: ACCEPTED

input
7
-774852389 498112692 -73382627...

correct output
7322574754.7929240637458860874...

user output
7322574754.792924

Test 40

Verdict: ACCEPTED

input
7
-745557241 -362230062 11872950...

correct output
7345290128.8702740180306136608...

user output
7345290128.8702755

Test 41

Verdict: ACCEPTED

input
7
-280510503 487323735 82609299 ...

correct output
8284167601.0197063554078340530...

user output
8284167601.019708

Test 42

Verdict: ACCEPTED

input
7
-194568921 -912512861 44703011...

correct output
9098246106.3207166725769639015...

user output
9098246106.320719

Test 43

Verdict: ACCEPTED

input
8
383287698 969195218 -182348842...

correct output
7016551085.8444829522632062435...

user output
7016551085.844481

Test 44

Verdict: ACCEPTED

input
8
-385704087 -937741013 -3077950...

correct output
8127710933.8054637983441352844...

user output
8127710933.805465

Test 45

Verdict: ACCEPTED

input
8
844450667 -871888619 -19960889...

correct output
8213584640.6935460437089204788...

user output
8213584640.693546

Test 46

Verdict: ACCEPTED

input
8
-466328566 481082051 -33685140...

correct output
9423990911.6089521860703825950...

user output
9423990911.608953

Test 47

Verdict: ACCEPTED

input
8
-917189424 -579600323 67525298...

correct output
8227519630.3055775831453502178...

user output
8227519630.305577

Test 48

Verdict: ACCEPTED

input
9
-31221656 -526597392 -52535813...

correct output
8856995290.3726284708827733993...

user output
8856995290.37263

Test 49

Verdict: ACCEPTED

input
9
-23884334 -938550432 -56172498...

correct output
7357984723.6206405288539826870...

user output
7357984723.620641

Test 50

Verdict: ACCEPTED

input
9
-114003248 747828772 -69571861...

correct output
7938964098.6173283923417329788...

user output
7938964098.61733

Test 51

Verdict: ACCEPTED

input
9
166708726 -263032442 565409766...

correct output
7766653103.2631514174863696098...

user output
7766653103.263151

Test 52

Verdict: ACCEPTED

input
9
-325935302 409170424 652212820...

correct output
8170515916.9658243129961192607...

user output
8170515916.965824

Test 53

Verdict: ACCEPTED

input
10
178568022 273124119 535857466 ...

correct output
8231356926.8400429780595004558...

user output
8231356926.840042

Test 54

Verdict: ACCEPTED

input
10
-104452078 546885062 -99975436...

correct output
9390756029.7148792939260601997...

user output
9390756029.714878

Test 55

Verdict: ACCEPTED

input
10
-63708076 -602539257 -94432385...

correct output
8497255968.9021178991533815860...

user output
8497255968.902117

Test 56

Verdict: ACCEPTED

input
10
182829493 -848119476 520735868...

correct output
9795917686.1810622680932283401...

user output
9795917686.181063

Test 57

Verdict: ACCEPTED

input
10
934069847 175172315 -629139614...

correct output
10107572824.729460356757044792...

user output
10107572824.72946

Test 58

Verdict: ACCEPTED

input
10
-523273295 -881501593 86988338...

correct output
9378626642.9278714880347251892...

user output
9378626642.927872

Test 59

Verdict: ACCEPTED

input
10
917402565 -287078799 -55030325...

correct output
9067761971.7593543389812111854...

user output
9067761971.759354

Test 60

Verdict: ACCEPTED

input
10
-836129193 -511793054 67486286...

correct output
9294216739.0473321685567498207...

user output
9294216739.047333

Test 61

Verdict: ACCEPTED

input
10
875675361 -976131926 -48580743...

correct output
10188158256.107221888378262519...

user output
10188158256.10722

Test 62

Verdict: ACCEPTED

input
10
-977721665 -217325906 77767487...

correct output
9173124717.6331664901226758956...

user output
9173124717.633167