DP(動的計画法)で解くことができます。

dpの定義

\(dp[i] :=(X_1,X_2,\ldots,X_i)\) まで考慮したとき、\(X_i = A_i\) としてよいか
\(ep[i] :=(X_1,X_2,\ldots,X_i)\) まで考慮したとき、\(X_i = B_i\) としてよいか

と \(dp,ep\) を定義します。

dpの初期値

\(dp[1]\) は、「\(X_1\) まで考慮したとき、\(X_1=A_1\) としてよいか」という意味であり、これは True です。
\(ep[1]\) も同様に True です。

dpの遷移

\(i\geq 2\) に対し、\(dp[i]\) を求めます。

• \(dp[i-1]=True\) かつ \(|A_{i-1}- A_i| \leq K\) ならば、\(dp[i]=True\)
• \(ep[i-1]=True\) かつ \(|B_{i-1}- A_i| \leq K\) ならば、\(dp[i]=True\)
  
• それ以外ならば、\(dp[i]=False\)

です。 \(ep[i]\) も同様に求めることができます。

問題の答え

\(dp[N]=True\) または \(ep[N]=True\) ならば、答えは Yes です。それ以外ならば答えは No です。

以上でこの問題を解くことができました。計算量は \(O(N)\) です。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;


signed main(){
    ll n,k;cin>>n>>k;
    vector<ll>a(n+1),b(n+1);
    for(ll i=1;i<=n;i++)cin>>a[i];
    for(ll i=1;i<=n;i++)cin>>b[i];
    vector<ll>dp(n+1,false),ep(n+1,false);

    //初期値
    dp[1]=ep[1]=true;

    //遷移
    for(ll i=2;i<=n;i++){
        if(dp[i-1]){
            if(abs(a[i-1]-a[i])<=k)dp[i]=true;
            if(abs(a[i-1]-b[i])<=k)ep[i]=true;
        }
        if(ep[i-1]){
            if(abs(b[i-1]-a[i])<=k)dp[i]=true;
            if(abs(b[i-1]-b[i])<=k)ep[i]=true;
        }
    }

    //答え
    if(dp[n]||ep[n])cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

    return 0;
}