Build an Electrical Grid
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!