Build an Electrical Grid The Challenge

There are N cities aligned in a straight line. The i-th city is located A[i] kilometers to the right of the origin. No two cities will be in the same place.

You are going to build an electrical grid with some power plants. Power plants must be built inside a city. However, you are only allowed to build K (&lt; N) power plants, so there will be some cities with no power plants in them. For each city with no power plants, you must build a cable between it and the nearest city that has a power plant.

For example, if there are three cities located at 0, 1, 2, and only the city at 0 has a power plant, you need to build two cables, one from 2 to 0(2km) and the other from 1 to 0(1km), which have a total length of 3km.

Given K and positions of cities (A), you should compute the minimum kilometers of cable you need to build the grid. 

Example Testcases

K = 1, A = [0, 2, 4, 6, 8] : 12 
# build power plant in the city at position 4, total length = 4 + 2 + 0 + 2 + 4 = 12

K = 3, A = [0, 1, 10, 11, 20, 21, 22, 30, 32] : 23
# build power plants in cities at positions 0, 10 and 22

K = 5, A = [0, 1, 3, 6, 8, 11, 14] : 3
# build power plants in all cities except those at positions 0, 3

K = 6, A = [0, 1, 3, 6, 8, 14, 15, 18, 29, 30, 38, 41, 45, 46, 49, 58, 66, 72, 83, 84] : 49


Specifications


You should implement a function or a program, which takes a positive integer K and a list of integers A in any form, and output/return an integer representing the answer.
A is sorted in ascending order, and all elements are non-negative integers.
A[0] = 0, and A[N-1] will be no more than 1000N.
Note that the output will be in magnitude of 1000N2, so in larger cases, you may need 64-bit integers in some languages.
Multithreading is not allowed (I will set the affinity of your program to only 1 core when judging). Compiler optimizations (such as -O2 in C) are allowed.


Scoring


I will time your code on my computer (Ubuntu 16.04 with Intel i7-3770S processor) with different size of testcases. Specifically, I will generate some testcases with N = floor(2x/5) where x is a positive integer.Your score will be the x value of the smallest testcase that your program uses more than 10 seconds or 1 GiB of memory, or doesn't give a correct answer.


The answer with highest score wins. If two answers get the same score, the earlier answer wins.

All programs will be judged by the same set of testcases. 
Feel free to post your own scorings. Explanations of your algorithm are encouraged.


Bonus

This is my C++ program, it scores 108. You can verify the SHA-256 digest 9a87fa183bad1e3a83d2df326682598796a216b3a4262c32f71dfb06df12935d by the whole code segment (without footer) in the link.

The algorithm combines binary search and Knuth's optimization to find the correct penalty of each plant to get the desired number. The complexity is O(N log N log A[N-1]). I was surprised that the program got a higher score than the O(N log A[N−1]) solution by Anders Kaseorg. It's probably due to the fact that the log case in Knuth's optimization won't usually occur.

Note that this challenge is the same as IOI 2000 Post Office. The original constraints are N &lt;= 300 and K &lt;= 30, though.
Rust, score = 104

This is an implementation of the algorithm noted by Grønlund et al. (2017) at the end of §3.3.1, though I had to follow a long citation chain and fill in some missing details.  It runs in O(N log A[N − 1]) time.

Compile with rustc -O. Input format is K on the first line, followed by the entries of A, one entry per line, all on stdin.

(Note: I’m submitting this an hour after the bounty deadline, but I expect the last version I submitted before the bounty deadline, which ran in O(N log N log A[N − 1]) time, to score about 94.)



use std::cmp::min;
use std::io::{self, BufRead};
use std::iter::{once, Cloned};
use std::num::Wrapping;
use std::ops::Range;
use std::slice;
use std::time::Instant;
use std::u64;

type Cost = u64;
const INF: Cost = u64::MAX;

trait ColsTrait&lt;Col&gt;: Clone {
    type Iter: Iterator&lt;Item = Col&gt;;
    fn len(&amp;self) -&gt; usize;
    fn iter(&amp;self) -&gt; Self::Iter;
    fn slice(&amp;self, range: Range&lt;usize&gt;) -&gt; Self;
}

impl&lt;'a, Col: Clone&gt; ColsTrait&lt;Col&gt; for &amp;'a [Col] {
    type Iter = Cloned&lt;slice::Iter&lt;'a, Col&gt;&gt;;
    fn len(&amp;self) -&gt; usize {
        (*self).len()
    }
    fn iter(&amp;self) -&gt; Self::Iter {
        (*self).iter().cloned()
    }
    fn slice(&amp;self, range: Range&lt;usize&gt;) -&gt; Self {
        unsafe { self.get_unchecked(range) }
    }
}

impl ColsTrait&lt;usize&gt; for Range&lt;usize&gt; {
    type Iter = Range&lt;usize&gt;;
    fn len(&amp;self) -&gt; usize {
        self.end - self.start
    }
    fn iter(&amp;self) -&gt; Range&lt;usize&gt; {
        self.clone()
    }
    fn slice(&amp;self, range: Range&lt;usize&gt;) -&gt; Self {
        Range {
            start: self.start + range.start,
            end: self.start + range.end,
        }
    }
}

fn smawk&lt;Col: Copy, Cols: ColsTrait&lt;Col&gt;, Key: Ord, F: Copy + Fn(usize, Col) -&gt; Key&gt;(
    n: usize,
    shift: u32,
    cols: Cols,
    f: F,
) -&gt; Vec&lt;usize&gt; {
    if n == 0 {
        Vec::new()
    } else if cols.len() &gt; n {
        let mut s = Vec::with_capacity(n);
        let mut sk = Vec::with_capacity(n);
        for (jk, j) in cols.iter().enumerate() {
            while match s.last() {
                Some(&amp;l) =&gt; f(!(!(s.len() - 1) &lt;&lt; shift), j) &lt;= f(!(!(s.len() - 1) &lt;&lt; shift), l),
                None =&gt; false,
            } {
                s.pop();
                sk.pop();
            }
            if s.len() &lt; n {
                s.push(j);
                sk.push(jk);
            }
        }
        smawk1(
            n,
            shift,
            cols,
            f,
            smawk(n / 2, shift + 1, &amp;s[..], f)
                .into_iter()
                .map(|h| unsafe { *sk.get_unchecked(h) }),
        )
    } else {
        smawk1(
            n,
            shift,
            cols.clone(),
            f,
            smawk(n / 2, shift + 1, cols, f).into_iter(),
        )
    }
}

fn smawk1&lt;
    Col: Copy,
    Cols: ColsTrait&lt;Col&gt;,
    Key: Ord,
    F: Fn(usize, Col) -&gt; Key,
    Iter: Iterator&lt;Item = usize&gt;,
&gt;(
    n: usize,
    shift: u32,
    cols: Cols,
    f: F,
    iter: Iter,
) -&gt; Vec&lt;usize&gt; {
    let mut out = Vec::with_capacity(n);
    let mut range = 0..0;
    for (i, k) in iter.enumerate() {
        range.end = k + 1;
        out.push(
            range
                .clone()
                .zip(cols.slice(range.clone()).iter())
                .min_by_key(|&amp;(_, col)| f(!(!(2 * i) &lt;&lt; shift), col))
                .unwrap()
                .0,
        );
        out.push(k);
        range.start = k;
    }
    if n % 2 == 1 {
        range.end = cols.len();
        out.push(
            range
                .clone()
                .zip(cols.slice(range.clone()).iter())
                .min_by_key(|&amp;(_, col)| f(!(!(n - 1) &lt;&lt; shift), col))
                .unwrap()
                .0,
        );
    }
    out
}

fn solve(k: usize, a: &amp;[Cost]) -&gt; Cost {
    if k &gt;= a.len() {
        return 0;
    }
    let sa = once(Wrapping(0))
        .chain(a.iter().scan(Wrapping(0), |s, &amp;x| {
            *s += Wrapping(x);
            Some(*s)
        }))
        .collect::&lt;Vec&lt;_&gt;&gt;();
    let c = |i: usize, j: usize| {
        let h = (i - j) / 2;
        unsafe {
            (sa.get_unchecked(i) - sa.get_unchecked(i - h) - sa.get_unchecked(j + h)
                + sa.get_unchecked(j))
                .0
        }
    };
    let cost1 = c(a.len(), 0);
    if k == 1 {
        return cost1;
    }
    let cost2 = (1..a.len()).map(|j| c(j, 0) + c(a.len(), j)).min().unwrap();
    let mut low = 0;
    let mut high = cost1 - cost2;
    let mut ret = INF;
    while low &lt;= high {
        let penalty = low + (high - low) / 2;
        let mut out = vec![(INF, 0); a.len() + 1];
        out[0] = (0, 0);
        let mut begin = 0;
        let mut chunk = 1;
        loop {
            let r = min(a.len() + 1 - begin, 2 * chunk);
            let edge = begin + chunk;
            let (out0, out1) = out.split_at_mut(edge);
            let f = |i: usize, j: usize| {
                let h = (edge + i - j) / 2;
                let &amp;(cost, count) = unsafe { out0.get_unchecked(j) };
                (
                    cost.saturating_add(
                        unsafe {
                            sa.get_unchecked(edge + i) - sa.get_unchecked(edge + i - h)
                                - sa.get_unchecked(j + h)
                                + sa.get_unchecked(j)
                        }.0 + penalty,
                    ),
                    count + 1,
                )
            };
            for ((i, j), o) in smawk(r - chunk, 0, begin..edge, &amp;f)
                .into_iter()
                .enumerate()
                .zip(out1.iter_mut())
            {
                *o = min(f(i, begin + j), *o);
            }
            let x = unsafe { out1.get_unchecked(r - 1 - chunk) };
            if let Some(j) = (edge..begin + r - 1).find(|&amp;j| &amp;f(r - 1 - chunk, j) &lt;= x) {
                begin = j;
                chunk = 1;
            } else if r == a.len() + 1 - begin {
                break;
            } else {
                chunk *= 2;
            }
        }
        let &amp;(cost, count) = unsafe { out.get_unchecked(a.len()) };
        if count &gt; k {
            low = penalty + 1;
        } else {
            ret = cost.wrapping_sub(k as Cost * penalty);
            if count == k {
                return ret;
            }
            high = penalty - 1;
        }
    }
    ret
}

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();
    let k = lines.next().unwrap().unwrap().parse().unwrap();
    let a = lines
        .map(|s| s.unwrap().parse().unwrap())
        .collect::&lt;Vec&lt;_&gt;&gt;();
    let start = Instant::now();
    let cost = solve(k, &amp;a);
    let time = start.elapsed();
    println!(
        "cost: {}\ntime: {}.{:09} sec",
        cost,
        time.as_secs(),
        time.subsec_nanos()
    );
}


Try it online!

Rust, pretest score = 73

Compile with rustc -O.  Input format is K on the first line, followed by the entries of A, one entry per line, all on stdin.



use std::io::{self, BufRead};
use std::iter::once;
use std::num::Wrapping;
use std::time::Instant;
use std::u64;

type Cost = u64;
const INF: Cost = u64::MAX;

fn smawk&lt;Col: Clone, Key: Ord, F: Clone + Fn(usize, &amp;Col) -&gt; Key&gt;(
    n: usize,
    shift: u32,
    cols: &amp;[Col],
    f: F,
) -&gt; Vec&lt;usize&gt; {
    if n == 0 {
        Vec::new()
    } else if cols.len() &gt; n {
        let mut s = Vec::with_capacity(n);
        let mut sk = Vec::with_capacity(n);
        for (jk, j) in cols.iter().enumerate() {
            while match s.last() {
                Some(l) =&gt; f(!(!(s.len() - 1) &lt;&lt; shift), j) &lt;= f(!(!(s.len() - 1) &lt;&lt; shift), l),
                None =&gt; false,
            } {
                s.pop();
                sk.pop();
            }
            if s.len() &lt; n {
                s.push(j.clone());
                sk.push(jk);
            }
        }
        smawk1(
            n,
            shift,
            cols,
            f.clone(),
            smawk(n / 2, shift + 1, &amp;s, f)
                .into_iter()
                .map(|h| unsafe { *sk.get_unchecked(h) }),
        )
    } else {
        smawk1(
            n,
            shift,
            cols,
            f.clone(),
            smawk(n / 2, shift + 1, &amp;cols, f).into_iter(),
        )
    }
}

fn smawk1&lt;Col: Clone, Key: Ord, F: Clone + Fn(usize, &amp;Col) -&gt; Key, Iter: Iterator&lt;Item = usize&gt;&gt;(
    n: usize,
    shift: u32,
    cols: &amp;[Col],
    f: F,
    iter: Iter,
) -&gt; Vec&lt;usize&gt; {
    let mut out = Vec::with_capacity(n);
    let mut range = 0..0;
    for (i, k) in iter.enumerate() {
        range.end = k + 1;
        out.push(
            range
                .clone()
                .zip(unsafe { cols.get_unchecked(range.clone()) })
                .min_by_key(|&amp;(_, col)| f(!(!(2 * i) &lt;&lt; shift), col))
                .unwrap()
                .0,
        );
        out.push(k);
        range.start = k;
    }
    if n % 2 == 1 {
        range.end = cols.len();
        out.push(
            range
                .clone()
                .zip(unsafe { cols.get_unchecked(range.clone()) })
                .min_by_key(|&amp;(_, col)| f(!(!(n - 1) &lt;&lt; shift), col))
                .unwrap()
                .0,
        );
    }
    out
}

fn solve(k: usize, a: &amp;[Cost]) -&gt; Cost {
    let mut cost = vec![INF; a.len() + 1 - k];
    let sa = once(Wrapping(0))
        .chain(a.iter().scan(Wrapping(0), |s, &amp;x| {
            *s += Wrapping(x);
            Some(*s)
        }))
        .collect::&lt;Vec&lt;_&gt;&gt;();
    cost[0] = 0;
    let cols = (0..a.len() + 1 - k).collect::&lt;Vec&lt;_&gt;&gt;();
    for m in 0..k {
        cost = {
            let f = |i: usize, &amp;j: &amp;usize| {
                if i + 1 &gt;= j {
                    let h = (i + 1 - j) / 2;
                    unsafe {
                        cost.get_unchecked(j).saturating_add(
                            (sa.get_unchecked(i + m + 1) - sa.get_unchecked(i + m + 1 - h)
                                - sa.get_unchecked(j + m + h)
                                + sa.get_unchecked(j + m))
                                .0,
                        )
                    }
                } else {
                    INF
                }
            };
            smawk(a.len() + 1 - k, 0, &amp;cols, &amp;f)
                .into_iter()
                .enumerate()
                .map(|(i, j)| f(i, &amp;j))
                .collect()
        };
    }
    cost[a.len() - k]
}

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();
    let k = lines.next().unwrap().unwrap().parse().unwrap();
    let a = lines
        .map(|s| s.unwrap().parse().unwrap())
        .collect::&lt;Vec&lt;_&gt;&gt;();
    let start = Instant::now();
    let cost = solve(k, &amp;a);
    let time = start.elapsed();
    println!(
        "cost: {}\ntime: {}.{:09} sec",
        cost,
        time.as_secs(),
        time.subsec_nanos()
    );
}


Try it online!