\(N (K+1)(C+1) \le 2 \times 10^7\) が重要な制約です。

動的計画法 (DP) でこの問題を解くことを考えます。
以下の DP テーブルを保持します。

\(dp[c][k]=\{\) 総重量が \(c\) 、使った軽量化ケースが \(k\) 個である場合の価値の総和の最大値 \(\}\)

この DP テーブル全体を \(N\) 回舐めるような解法は時間計算量 \(O(N(K+1)(C+1))\) となりこの問題に正解できます。そのようなものを立案しましょう。

• \(i=C,C-1,\dots,0\) について、以下を繰り返す。
  • \(j=K,K-1,\dots,0\) について、以下を繰り返す。
    • \(dp[i][j]\) から、軽量化ケースを使わず宝石を運搬するための遷移を行う。
    • \(dp[i][j]\) から、軽量化ケースを使って宝石を運搬するための遷移を行う。

詳細な遷移式は読者への宿題とします(実装例にも記しています)。

なお、軽量化ケースによって宝石の重さが \(0\) になる場合があります。このことから、特に DP にて in-place (DPテーブルをひとつで済ませる) な実装をする場合、ループの回し方には十分注意しましょう。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
  ll N,C,K;
  cin >> N >> C >> K;
  vector<vector<ll>> dp(C+1,vector<ll>(K+1,-1e18));
  dp[0][0]=0;
  for(ll jw=0;jw<N;jw++){
    ll B,W;
    cin >> B >> W;
    for(ll i=C;i>=0;i--){
      for(ll j=K;j>=0;j--){
        if(dp[i][j]<0){continue;}
        if(i+W<=C){
          dp[i+W][j]=max(dp[i+W][j],dp[i][j]+B);
        }
        if(i+(W/2)<=C && j+1<=K){
          dp[i+(W/2)][j+1]=max(dp[i+(W/2)][j+1],dp[i][j]+B);
        }
      }
    }
  }
  ll res=0;
  for(auto &nx : dp){
    for(auto &ny : nx){res=max(res,ny);}
  }
  cout << res << "\n";
  return 0;
}