Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Forget the word “subsequence” for a second. Since cost only depends on the elements inside each part and its length, a partition is just coloring every element with one of colors, each color used at least once. Order is a red herring here.
If the group sizes are fixed, say , each element in group gets multiplied by . So we have copies of coefficient . By rearrangement, sort increasingly and put the largest coefficients on the smallest values.
A group of size contributes a block of equal coefficients . After sorting coefficients descending, the answer is obtained by partitioning sorted into contiguous blocks, where a block of length costs times its sum.
Now the problem is: split sorted into non-empty contiguous segments minimizing . Direct DP is or worse, and can be huge. Need a Lagrangian trick: charge a fixed penalty per segment and minimize .
For a fixed penalty , compute the minimum penalized cost and the number of segments it uses. The transition is . Rewrite it as lines in and maintain a Li Chao tree. Binary search until the optimal solution uses at least/at most segments, then subtract to recover the exact- answer.
First, kill the fake difficulty
The statement says “subsequences”, which sounds like there is some nasty ordering constraint. There isn't. A subset of positions, read in original order, is always a subsequence, so partitioning into subsequences is exactly the same as assigning every element to one of non-empty groups.
For one group of length ,
So every element placed in that group is multiplied by .
Suppose the group sizes are fixed:
Then the coefficient multiset is:
To minimize the dot product with the values , by rearrangement we should pair larger coefficients with smaller values. Therefore sort
Now the problem becomes:
Split sorted into exactly non-empty contiguous segments. A segment of length costs
That is the real problem. The subsequence wording was just smoke and mirrors. Classic CF bullshit, but legal.
DP form
Let
For a segment , its cost is
The exact DP would be
But , so doing this for all is dead on arrival.
Lagrangian relaxation
Instead of forcing exactly segments, charge a penalty for every segment and minimize:
For a fixed , define as the minimum penalized cost for the prefix .
and
Alongside , store , the number of segments used in the optimal penalized solution. When costs tie, choose the solution with more segments. That makes the segment count monotone nicely while binary searching.
As increases, using another segment becomes more expensive, so the optimal number of segments never increases. We can binary search the largest such that the optimum uses at least segments.
If the fixed-penalty optimum at this is
then for exactly segments the answer is recovered as
Why does this work? At the boundary value of , the lower envelope supports an optimum with segments, or at least the same adjusted value. This is the usual alien trick / slope trick thing: penalize the count, binary search the multiplier, subtract it back. Fancy name, simple idea.
Optimizing one check
Now we need to compute, for fixed :
Expand the transition:
So for fixed , the part depending on is:
Let each previous define a function evaluated at query index :
Then
This is not a normal one-variable line because appears too. But all query points are known in advance, so use a discrete Li Chao tree over indices . A stored function only needs an eval(i) method.
Each function stores:
When two functions give the same value, prefer the one with larger segment count. Since transition adds one segment, a stored function also carries .
Then:
Insert the function for this and continue.
Important numeric detail
The true answer can be around , which is about , past signed 64-bit. Use __int128 for DP and output it manually.
Full plan
Total complexity:
with , which is fine.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
const i128 INF = (((i128)1) << 120);
struct State {
i128 val;
int cnt;
};
bool better(State a, State b) {
if (a.val != b.val) return a.val < b.val;
return a.cnt > b.cnt;
}
struct Line {
i128 p;
int j;
i128 base;
int cnt;
bool empty;
Line() : p(0), j(0), base(0), cnt(-1), empty(true) {}
Line(i128 _p, int _j, i128 _base, int _cnt)
: p(_p), j(_j), base(_base), cnt(_cnt), empty(false) {}
};
struct LiChao {
int n;
const vector<i128> &pref;
vector<Line> tree;
LiChao(int _n, const vector<i128> &_pref) : n(_n), pref(_pref), tree(4 * _n + 4) {}
State eval(const Line &ln, int x) const {
if (ln.empty) return {INF, -1};
i128 v = -ln.p * x - (i128)ln.j * pref[x] + ln.base;
return {v, ln.cnt};
}
void add_line(Line nw, int node, int l, int r) {
if (tree[node].empty) {
tree[node] = nw;
return;
}
int mid = (l + r) >> 1;
Line lo = tree[node], hi = nw;
if (better(eval(hi, mid), eval(lo, mid))) swap(lo, hi);
tree[node] = lo;
if (l == r) return;
if (better(eval(hi, l), eval(lo, l))) {
add_line(hi, node << 1, l, mid);
} else if (better(eval(hi, r), eval(lo, r))) {
add_line(hi, node << 1 | 1, mid + 1, r);
}
}
void add_line(Line ln) {
add_line(ln, 1, 1, n);
}
State query(int x, int node, int l, int r) const {
State res = eval(tree[node], x);
if (l == r) return res;
int mid = (l + r) >> 1;
State got = (x <= mid)
? query(x, node << 1, l, mid)
: query(x, node << 1 | 1, mid + 1, r);
return better(got, res) ? got : res;
}
State query(int x) const {
return query(x, 1, 1, n);
}
};
string to_string_i128(i128 x) {
if (x == 0) return "0";
bool neg = x < 0;
if (neg) x = -x;
string s;
while (x > 0) {
s.push_back(char('0' + x % 10));
x /= 10;
}
if (neg) s.push_back('-');
reverse(s.begin(), s.end());
return s;
}
State solve_penalty(const vector<i128> &pref, i128 penalty) {
int n = (int)pref.size() - 1;
vector<State> dp(n + 1);
LiChao lichao(n, pref);
dp[0] = {0, 0};
lichao.add_line(Line(pref[0], 0, dp[0].val, dp[0].cnt));
for (int i = 1; i <= n; i++) {
State best = lichao.query(i);
dp[i] = {(i128)i * pref[i] + penalty + best.val, best.cnt + 1};
lichao.add_line(Line(pref[i], i, dp[i].val + (i128)i * pref[i], dp[i].cnt));
}
return dp[n];
}
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n, k;
cin >> n >> k;
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a.begin() + 1, a.end());
vector<i128> pref(n + 1, 0);
for (int i = 1; i <= n; i++) pref[i] = pref[i - 1] + (i128)a[i];
i128 lo = -((i128)1 << 100), hi = ((i128)1 << 100);
while (lo < hi) {
i128 mid = (lo + hi + 1) / 2;
State cur = solve_penalty(pref, mid);
if (cur.cnt >= k) lo = mid;
else hi = mid - 1;
}
State best = solve_penalty(pref, lo);
cout << to_string_i128(best.val - (i128)k * lo) << '\n';
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
const i128 INF = (((i128)1) << 120);
struct State {
i128 val;
int cnt;
};
bool better(State a, State b) {
if (a.val != b.val) return a.val < b.val;
return a.cnt > b.cnt;
}
struct Line {
i128 p;
int j;
i128 base;
int cnt;
bool empty;
Line() : p(0), j(0), base(0), cnt(-1), empty(true) {}
Line(i128 _p, int _j, i128 _base, int _cnt)
: p(_p), j(_j), base(_base), cnt(_cnt), empty(false) {}
};
struct LiChao {
int n;
const vector<i128> &pref;
vector<Line> tree;
LiChao(int _n, const vector<i128> &_pref) : n(_n), pref(_pref), tree(4 * _n + 4) {}
State eval(const Line &ln, int x) const {
if (ln.empty) return {INF, -1};
i128 v = -ln.p * x - (i128)ln.j * pref[x] + ln.base;
return {v, ln.cnt};
}
void add_line(Line nw, int node, int l, int r) {
if (tree[node].empty) {
tree[node] = nw;
return;
}
int mid = (l + r) >> 1;
Line lo = tree[node], hi = nw;
if (better(eval(hi, mid), eval(lo, mid))) swap(lo, hi);
tree[node] = lo;
if (l == r) return;
if (better(eval(hi, l), eval(lo, l))) {
add_line(hi, node << 1, l, mid);
} else if (better(eval(hi, r), eval(lo, r))) {
add_line(hi, node << 1 | 1, mid + 1, r);
}
}
void add_line(Line ln) {
add_line(ln, 1, 1, n);
}
State query(int x, int node, int l, int r) const {
State res = eval(tree[node], x);
if (l == r) return res;
int mid = (l + r) >> 1;
State got = (x <= mid)
? query(x, node << 1, l, mid)
: query(x, node << 1 | 1, mid + 1, r);
return better(got, res) ? got : res;
}
State query(int x) const {
return query(x, 1, 1, n);
}
};
string to_string_i128(i128 x) {
if (x == 0) return "0";
bool neg = x < 0;
if (neg) x = -x;
string s;
while (x > 0) {
s.push_back(char('0' + x % 10));
x /= 10;
}
if (neg) s.push_back('-');
reverse(s.begin(), s.end());
return s;
}
State solve_penalty(const vector<i128> &pref, i128 penalty) {
int n = (int)pref.size() - 1;
vector<State> dp(n + 1);
LiChao lichao(n, pref);
dp[0] = {0, 0};
lichao.add_line(Line(pref[0], 0, dp[0].val, dp[0].cnt));
for (int i = 1; i <= n; i++) {
State best = lichao.query(i);
dp[i] = {(i128)i * pref[i] + penalty + best.val, best.cnt + 1};
lichao.add_line(Line(pref[i], i, dp[i].val + (i128)i * pref[i], dp[i].cnt));
}
return dp[n];
}
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n, k;
cin >> n >> k;
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a.begin() + 1, a.end());
vector<i128> pref(n + 1, 0);
for (int i = 1; i <= n; i++) pref[i] = pref[i - 1] + (i128)a[i];
i128 lo = -((i128)1 << 100), hi = ((i128)1 << 100);
while (lo < hi) {
i128 mid = (lo + hi + 1) / 2;
State cur = solve_penalty(pref, mid);
if (cur.cnt >= k) lo = mid;
else hi = mid - 1;
}
State best = solve_penalty(pref, lo);
cout << to_string_i128(best.val - (i128)k * lo) << '\n';
}
return 0;
}