C++ 解法, 执行用时: 400ms, 内存消耗: 2860K, 提交时间: 2021-09-12 17:57:06

#include<bits/stdc++.h>
using namespace std;
int N,K;
int D[20005];
int S[20005];
long long C[20005];
long long W[20005];
long long dp[20005];
vector<int>v[20005];
struct node
{
    long long mi;
    long long lazy;
}A[80020];
void bt(int k,int l,int r)
{
    A[k].lazy=0;
    if(l==r)
    {
        A[k].mi=dp[l];
        return;
    }
    int mid=l+r>>1;
    bt(k<<1,l,mid);
    bt(k<<1|1,mid+1,r);
    A[k].mi=min(A[k<<1].mi,A[k<<1|1].mi);
    return;
}
void pd(int k)
{
    A[k<<1].mi+=A[k].lazy;
    A[k<<1|1].mi+=A[k].lazy;
    A[k<<1].lazy+=A[k].lazy;
    A[k<<1|1].lazy+=A[k].lazy;
    A[k].lazy=0;
    return;
}
void cg(int k,int l,int r,int z,int y,int x)
{
    if(z>y)
    {
        return;
    }
    if(l>=z&&r<=y)
    {
        A[k].mi+=x;
        A[k].lazy+=x;
        return;
    }
    if(A[k].lazy)
    {
        pd(k);
    }
    int mid=l+r>>1;
    if(z<=mid)
    {
        cg(k<<1,l,mid,z,y,x);
    }
    if(y>mid)
    {
        cg(k<<1|1,mid+1,r,z,y,x);
    }
    A[k].mi=min(A[k<<1].mi,A[k<<1|1].mi);
    return;
}
long long cx(int k,int l,int r,int z,int y)
{
    if(z>y)
    {
        return 0;
    }
    if(l>=z&&r<=y)
    {
        return A[k].mi;
    }
    long long ans=0x3f3f3f3f3f3f3f3f;
    int mid=l+r>>1;
    if(z<=mid)
    {
        ans=min(ans,cx(k<<1,l,mid,z,y));
    }
    if(y>mid)
    {
        ans=min(ans,cx(k<<1|1,mid+1,r,z,y));
    }
    return ans;
}
int main()
{
    scanf("%d %d",&N,&K);
    for(int i=2;i<=N;i++)
    {
        scanf("%d",D+i);
    }
    for(int i=1;i<=N;i++)
    {
        scanf("%d",C+i);
    }
    for(int i=1;i<=N;i++)
    {
        scanf("%d",S+i);
        v[upper_bound(D+i,D+N+1,D[i]+S[i])-D-1].push_back(i);
    }
    for(int i=1;i<=N;i++)
    {
        scanf("%d",W+i);
    }
    N++;
    K++;
    D[N]=0x3f3f3f3f;
    W[N]=0x3f3f3f3f3f3f3f3f;
    long long t=0;
    for(int i=1;i<=N;i++)
    {
        dp[i]=t+C[i];
        for(auto it:v[i])
        {
            t+=W[it];
        }
    }
    for(int k=2;k<=K;k++)
    {
        bt(1,1,N);
        for(int i=1;i<=N;i++)
        {
            dp[i]=min(dp[i],cx(1,1,N,1,i-1)+C[i]);
            for(auto it:v[i])
            {
                cg(1,1,N,1,lower_bound(D+1,D+it+1,D[it]-S[it])-D-1,W[it]);
            }
        }
    }
    printf("%lld\n",dp[N]);
    return 0;
}