区間を \(L_i\) の昇順にソートした上で、以下のような形の区間選択を考えます。

• 区間をひとつ採用する。
• 区間は \(L_i\) の昇順に並んでいるため、囲わずに飛ばした \(L_i\) 以前の部分はもう囲うことができない。

これをそのまま以下の DP(動的計画法) に落とします。
segtree を利用する必要があります。また、 \(K \le 10\) であることを利用します。

• \(dp[k][i]=\{\) 区間を \(k\) 個選択した上で、商品 \(i\) までを囲う・あるいは囲わないことを決定した際の囲わずに失った利益の最小値 \(\}\)

• \(dp[k]\) から \(dp[k+1]\) へと、以下の遷移をします。

  • \(\displaystyle \min_{i=0,1,\dots,L_i-1} dp[k][i]+(V[i+1]+V[i+2]+\dots+V[L_i-1])\)
  • \(\displaystyle \min_{i=L_i,L_i+1,\dots,R_i} dp[k][i]\)

後者は min を segtree に乗せればよく、前者は \(dp[k][i]+(V[i+1]+V[i+2]+\dots+V[N])\) を segtree に乗せることで単なる区間 min として処理できます。

計算量は \(O(NK+MK \log N)\) です。
なお、 \(L_i\) が同じもの同士では最大の \(R_i\) を持つものしか考慮しなくてよいという性質を使うと \(O(M+NK \log N)\) ともできます。

#include<bits/stdc++.h>
#include<atcoder/segtree>

using namespace std;
using namespace atcoder;

using ll=long long;

ll op(ll a,ll b){return min(a,b);}
ll e(){return 1e18;}

int main(){
  ll N,M,K;
  cin >> N >> M >> K;
  vector<ll> V(N+1);
  for(ll i=0;i<N;i++){
    cin >> V[i];
  }
  V[N]=0;
  for(ll i=N-1;i>=0;i--){ V[i]+=V[i+1]; }
  vector<pair<ll,ll>> cp(M);
  for(auto &nx : cp){
    cin >> nx.first >> nx.second;
    nx.first--; nx.second--;
  }
  sort(cp.begin(),cp.end());

  vector<ll> ini(N+1,e());
  segtree<ll,op,e> bas(ini);
  vector<segtree<ll,op,e>> seg_flat(K+1,bas);
  vector<segtree<ll,op,e>> seg_slop(K+1,bas);
  seg_flat[0].set(0,0);
  seg_slop[0].set(0,V[0]);
  for(auto [l,r] : cp){
    for(ll i=0;i<K;i++){
      ll val=seg_flat[i].prod(l,r+1);
      val=min(val,seg_slop[i].prod(0,l)-V[l]);
      seg_flat[i+1].set(r+1,min(seg_flat[i+1].get(r+1),val));
      seg_slop[i+1].set(r+1,min(seg_slop[i+1].get(r+1),val+V[r+1]));
    }
  }
  ll res=e();
  for(ll i=0;i<=K;i++){
    res=min(res,seg_slop[i].all_prod());
  }
  // cout << res << "\n";
  cout << V[0]-res << "\n";
  return 0;
}