バリケードの条件を整理しましょう。
まず、 \(X_i=0\) なるバリケードが存在すれば座標 \(0\) から動けないため、答えは \(0\) です。以降、このようなケースを取り除いて考えます。

\(\sum |D_i| \le 5 \times 10^4\) という制約があるので、高橋君が動ける座標は \([-50000,50000]\) の範囲内であることがわかります。
このことから、この範囲外のバリケードは存在しないものとして考えて構いません。
また、重要なのは座標 \(0\) に正・負それぞれで最も近いバリケードです。それらが高橋君の動ける座標の範囲を支配します。

以下の動的計画法 (DP) を考えます。
\(dp[\) 高橋君の座標 \(x] = \{\) その時点で座標 \(x\) に高橋君が存在できるか \(\}\)
この DP を回すことができればこの問題に正解できます。
高橋君の存在しうる座標の範囲の大きさを \(R=10^5+1\) としたとき、時間計算量 \(O(NR)\) の DP は存在することがわかります。
このままでは実行時間制限に間に合いません。(部分和問題を含んでいるため、ここから劇的に高速化することも難しそうです。)
どうすればよいでしょうか。

DP が持つものがブール値なので、 bitset と呼ばれるデータ構造でこの DP を \(w\) 倍に高速化できます。( \(w\) はワードサイズと呼ばれる定数で、現代のコンピュータでは \(w=64\) 程度の定数であるとみなすことができます)
bitset といっても、ビット演算ができる長い bit 列であると考えればよいです。

今回の DP では、 DP テーブルを bitset として保持し、遷移を以下のようにかければよいです。

• \(D_i > 0\) のとき、元の DP テーブルと \(D_i\) だけ左シフトした DP テーブルとの OR を取る。
  • \(dp[i+D_i]\) に \(dp[i]\) を遷移させる行為に対応する。
• \(D_i < 0\) のとき、元の DP テーブルと \(-D_i\) だけ右シフトした DP テーブルとの OR を取る。
  • \(dp[i-D_i]\) に \(dp[i]\) を遷移させる行為に対応する。
• その後、高橋君が存在できる範囲を表現した bitset との AND を取る。
  • \(dp\) の範囲外に出てしまった遷移を取り除く。

時間計算量 \(O(NR/w)\) であれば額面で \(3 \times 10^8\) 程度であり、間に合うことがわかります。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int N,M;
  cin >> N >> M;
  vector<int> D(N);
  for(auto &nx : D){cin >> nx;}
  int low=-50005,high=50005;
  int ofs=50016;
  bool x0=false;
  for(int i=0;i<M;i++){
    int X;
    cin >> X;
    if(X==0){x0=true;}
    if(X<0){low=max(low,X+1);}
    if(X>0){high=min(high,X-1);}
  }
  if(x0){
    cout << "0\n";
    return 0;
  }

  bitset<100032> bs,mask;
  for(int i=0;i<100032;i++){
    int act=i-ofs;
    if(low<=act && act<=high){mask[i]=1;}
  }
  bs[ofs]=1;

  for(int i=0;i<N;i++){
    if(D[i]>0){bs|=(bs<<D[i]);}
    else{bs|=(bs>>(-D[i]));}
    bs&=mask;
  }
  for(int i=100031;i>=0;i--){
    if(bs[i]){
      cout << i-ofs << "\n";
      return 0;
    }
  }
  return 0;
}