解法

まず愚直DPを考えると、$i$番目まで見て$j$要素に分割したときの最小値

$$\mathrm{dp}(r, j + 1) = \min \left\{ \mathrm{dp}(l, j) + \left|\sum_{l \le i \lt r}a_i\right| \mid l \lt r \right\}$$

である。 とりあえず累積和$A_i$を取って左端は定数(典型)として処理したいが、絶対値関数が邪魔をして

$$\mathrm{dp}(r, j + 1) = \min \left( \min \left\{ \mathrm{dp}(l, j) - A_l \mid l \lt r \land A_l \le A_r \right\} + A_r, \; \min \left\{ \mathrm{dp}(l, j) + A_l \mid l \lt r \land A_l \ge A_r \right\} - A_r \right)$$

までで止まってしまう。 segment木による実家DPに持ち込みたいが、$A_l \le A_r$な$l$と$A_l \ge A_r$な$l$とが入り乱れてしまうために難しい。 そこで添字を$A_i$の順で整列(覚えておきたい)することを考える。 $\sigma(i) \le \sigma(j) \iff A_i \le A_j$なrank関数$\sigma$を取ると、適当な位置を$+ \infty$で初期化しておくことにより、

$$\mathrm{dp}(r, j + 1) = \min \left( \min \left\{ \mathrm{dp}(\sigma^{-1}(i), j) - A_{\sigma^{-1}(i)} \mid i \lt \sigma(r) \right\} + A_r, \; \min \left\{ \mathrm{dp}(\sigma^{-1}(i), j) + A_{\sigma^{-1}(i)} \mid i \gt \sigma(r) \right\} - A_r \right)$$

とできる。 これはsegment木で処理できる形である。 よって$O(NM\log N)$。

実装

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
#define REP_R(i, n) for (int i = int(n) - 1; (i) >= 0; -- (i))
#define ALL(x) begin(x), end(x)
using ll = long long;
using namespace std;
template <class T> inline void chmin(T & a, T const & b) { a = min(a, b); }

template <class Monoid>
struct segment_tree {
    typedef typename Monoid::underlying_type underlying_type;
    int n;
    vector<underlying_type> a;
    const Monoid mon;
    segment_tree() = default;
    segment_tree(int a_n, underlying_type initial_value = Monoid().unit(), Monoid const & a_mon = Monoid()) : mon(a_mon) {
        n = 1; while (n < a_n) n *= 2;
        a.resize(2 * n - 1, mon.unit());
        fill(a.begin() + (n - 1), a.begin() + ((n - 1) + a_n), initial_value); // set initial values
        REP_R (i, n - 1) a[i] = mon.append(a[2 * i + 1], a[2 * i + 2]); // propagate initial values
    }
    void point_set(int i, underlying_type z) { // 0-based
        a[i + n - 1] = z;
        for (i = (i + n) / 2; i > 0; i /= 2) { // 1-based
            a[i - 1] = mon.append(a[2 * i - 1], a[2 * i]);
        }
    }
    underlying_type range_concat(int l, int r) { // 0-based, [l, r)
        underlying_type lacc = mon.unit(), racc = mon.unit();
        for (l += n, r += n; l < r; l /= 2, r /= 2) { // 1-based loop, 2x faster than recursion
            if (l % 2 == 1) lacc = mon.append(lacc, a[(l ++) - 1]);
            if (r % 2 == 1) racc = mon.append(a[(-- r) - 1], racc);
        }
        return mon.append(lacc, racc);
    }
    underlying_type point_get(int i) { return range_concat(i, i + 1); }
};
struct min_monoid {
    typedef ll underlying_type;
    ll unit() const { return LLONG_MAX; }
    ll append(ll a, ll b) const { return min(a, b); }
};

constexpr ll inf = (ll)1e18 + 9;
int main() {
    // input
    int n, m; cin >> n >> m;
    vector<int> a(n); REP (i,n) cin >> a[i];

    // solve
    vector<ll> acc(n + 1);
    REP (i, n) acc[i + 1] = acc[i] + a[i];
    vector<int> order(n + 1);
    iota(ALL(order), 0);
    sort(ALL(order), [&](int i, int j) { return acc[i] < acc[j]; });
    vector<int> rank(n + 1);
    REP (i, n + 1) rank[order[i]] = i;

    vector<segment_tree<min_monoid> > dp_lo(m + 1, segment_tree<min_monoid>(n + 1, inf));
    vector<segment_tree<min_monoid> > dp_hi(m + 1, segment_tree<min_monoid>(n + 1, inf));
    dp_lo[0].point_set(rank[0], 0);
    dp_hi[0].point_set(rank[0], 0);
    REP (i, n) {
        REP_R (j, m + 1) {
            ll it = inf;
            chmin(it, dp_lo[j].range_concat(0, rank[i + 1])         + acc[i + 1]);
            chmin(it, dp_hi[j].range_concat(rank[i + 1] + 1, n + 1) - acc[i + 1]);
            dp_lo[min(m, j + 1)].point_set(rank[i + 1], it - acc[i + 1]);
            dp_hi[min(m, j + 1)].point_set(rank[i + 1], it + acc[i + 1]);
        }
    }

    // output
    ll answer = dp_lo[m].point_get(rank[n]) + acc[n];
    assert (answer == dp_hi[m].point_get(rank[n]) - acc[n]);
    cout << answer << endl;
    return 0;
}