1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
| #include <bits/stdc++.h>
using namespace std;
const long long INF_INT = 1000000000;
const long long INF = 1000000000000000000;
template<class TD, class TR, TR (*f)(vector<TD>)>
struct Lconvex {
int n;
Lconvex(int _n) : n(_n) {}
pair<TR, vector<TD>> min_scaling(vector<TD> x, TD alpha) const {
TR f0, f1 = f(x);
while (alpha) {
f0 = f1, f1 = min_cube(x, f0, alpha);
if (f0 == f1) alpha >>= 1;
}
return {f1, move(x)};
}
private:
TR min_cube(vector<TD> &x, TR f_best, const TD alpha) const {
vector<TD> x0{x};
for (int S = 1; S < (1 << n) - 1; S++) {
vector<TD> xS{x0};
for (int i = 0; i < n; i++) if (S >> i & 1) xS[i] += alpha;
TR fS = f(xS);
if (fS < f_best) f_best = fS, x = move(xS);
}
return f_best;
}
};
int n;
array<int, 4> x;
vector<array<int, 4>> c;
long long f(vector<int> q) {
long long res = 0;
for (int i = 0; i < n; i++) res += max({c[i][0] - q[0], c[i][1] - q[1], c[i][2] - q[2], c[i][3] - q[3]});
for (int j = 0; j < 4; j++) res += (long long) x[j] * q[j];
return res;
}
int main() {
int t;
cin >> t;
for (int i = 0; i < t; i++){
int b, k1, k2;
cin >> n >> b >> k1 >> k2;
vector<int> a(n);
for (int j = 0; j < n; j++){
cin >> a[j];
}
c.resize(n);
auto solve = [&](int A){
x[0] = n + A - k1 - k2;
x[1] = k1 - A;
x[2] = k2 - A;
x[3] = A;
for (int j = 0; j < n; j++){
c[j][0] = a[j];
c[j][1] = (a[j] + 1) / 2;
c[j][2] = max(a[j] - b, 0);
c[j][3] = min(max((a[j] + 1) / 2 - b, 0), (max(a[j] - b, 0) + 1) / 2);
}
for (int j = 0; j < n; j++){
for (int k = 0; k < 4; k++){
c[j][k] = INF_INT - c[j][k];
}
}
Lconvex<int, long long, f> lc(4);
return INF_INT * n - lc.min_scaling({0, 0, 0, 0}, 1 << 29).first;
};
int L = max(k1 + k2 - n, 0), R = min(k1, k2);
long long ans = min(solve(L), solve(R));
while (R - L > 2){
int ml = (L + R) / 2;
int mr = ml + 1;
long long sl = solve(ml);
long long sr = solve(mr);
ans = min({ans, sl, sr});
if (sl > sr){
L = ml;
} else {
R = mr;
}
}
ans = min(ans, solve((L + R) / 2));
cout << ans << endl;
}
}
|
