Sol
设(f[i][j])表示钦定(i)建基站，建了(j)个基站的最小代价
(f[i][j]=max(f[l][j-1]+Sigma_{t=l+1}^{i-1})不能影响到的村庄的(w[t])+c[i])
二分处理出每个村庄(p)左右能影响到它的最远的基站设为(L[p], R[p])
(l,i)不能影响到的即(L[p]>l, R[p]<i)
枚举(j)，预处理出(j=1)的情况
线段树
每次把上次的(f)重建进入线段树，维护最小值
再枚举(i)每次加入(R[p])小于(i)的覆盖(1,L[p])
我是做到(f[n+1])，然后做(k+1)遍直接输出(f[n+1])的
# include <bits/stdc++.h>
# define RG register
# define IL inline
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int _(1e5 + 5);
IL ll Input(){
RG ll x = 0, z = 1; RG char c = getchar();
for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
return x * z;
}
int n, k, d[_], s[_], w[_], c[_], l[_], r[_], first[_], nxt[_];
int mn[_ << 2], tag[_ << 2], f[_];
IL void Build(RG int x, RG int l, RG int r){
tag[x] = 0;
if(l == r){
mn[x] = f[l];
return;
}
RG int mid = (l + r) >> 1;
Build(x << 1, l, mid), Build(x << 1 | 1, mid + 1, r);
mn[x] = min(mn[x << 1], mn[x << 1 | 1]);
}
IL void Modify(RG int x, RG int l, RG int r, RG int L, RG int R, RG int v){
if(L <= l && R >= r){
mn[x] += v, tag[x] += v;
return;
}
RG int mid = (l + r) >> 1;
if(L <= mid) Modify(x << 1, l, mid, L, R, v);
if(R > mid) Modify(x << 1 | 1, mid + 1, r, L, R, v);
mn[x] = min(mn[x << 1], mn[x << 1 | 1]) + tag[x];
}
IL int Query(RG int x, RG int l, RG int r, RG int L, RG int R){
if(R < L) return 0;
if(L <= l && R >= r) return mn[x];
RG int mid = (l + r) >> 1, ans = 2e9;
if(L <= mid) ans = Query(x << 1, l, mid, L, R);
if(R > mid) ans = min(ans, Query(x << 1 | 1, mid + 1, r, L, R));
return ans + tag[x];
}
int main(RG int argc, RG char *argv[]){
Fill(first, -1), n = Input(), k = Input();
for(RG int i = 2; i <= n; ++i) d[i] = Input();
for(RG int i = 1; i <= n; ++i) c[i] = Input();
for(RG int i = 1; i <= n; ++i) s[i] = Input();
for(RG int i = 1; i <= n; ++i) w[i] = Input();
for(RG int i = 1; i <= n; ++i){
RG int L = 1, R = i;
while(L <= R){
RG int mid = (L + R) >> 1;
if(d[i] - d[mid] <= s[i]) R = mid - 1, l[i] = mid;
else L = mid + 1;
}
L = i, R = n;
while(L <= R){
RG int mid = (L + R) >> 1;
if(d[mid] - d[i] <= s[i]) L = mid + 1, r[i] = mid;
else R = mid - 1;
}
nxt[i] = first[r[i]], first[r[i]] = i;
}
for(RG int i = 1, g = 0; i <= n + 1; ++i){
f[i] = g + c[i];
for(RG int j = first[i]; j != -1; j = nxt[j]) g += w[j];
}
RG int ans = f[n + 1];
for(RG int p = 1; p <= k; ++p){
Build(1, 1, n);
for(RG int i = 1; i <= n + 1; ++i){
f[i] = Query(1, 1, n, 1, i - 1) + c[i];
for(RG int j = first[i]; j != -1; j = nxt[j])
if(l[j] > 1) Modify(1, 1, n, 1, l[j] - 1, w[j]);
}
ans = min(ans, f[n + 1]);
}
printf("%d
", ans);
return 0;
}