次のようなDPを考えます。

\(\mathrm{DP}[n][x]=\) \(n\) 番目の皿まで食べ終わった時点で、(高橋君の満足度)-(青木君の満足度)が \(x\) であるときの、高橋君の満足度の最大値

\(n+1\) 番目の皿を高橋君と青木君のどちらが取るかを考えることでこのDPテーブルを埋めることができます。状態数が \(O(NM)\)、遷移が \(O(1)\) であることから、全体で \(O(NM)\) でこの問題が解けました。

DPの第2添字は \(-M\) 以上 \(M\) 以下を考慮する必要があります。負の添字は扱いが面倒なため、

• 全体を \(M\) ずらして \(0\) 以上 \(2M\) 以下とする
• 配列ではなく辞書を用いてDPテーブルを保持する
• メモ化再帰で実装し、DPテーブルを陽に持たない

などのいずれかの工夫をするとよいでしょう。

writer解(Python)

N,M=map(int,input().split())

dp=[-10**9]*(2*M+1)
dp[M]=0

for _ in range(N):
  new_dp=[-10**9]*(2*M+1)
  a,b=map(int,input().split())
  for j in range(2*M+1):
    if 0<=j+a<=2*M and new_dp[j+a]<dp[j]+a: new_dp[j+a]=dp[j]+a
    if 0<=j-b<=2*M and new_dp[j-b]<dp[j]  : new_dp[j-b]=dp[j]
  dp=new_dp

print(max(-1,max(dp)))