第１１回日本情報オリンピック 予選（オンライン） D-パスタ(Pasta)(検討中）

atcoder.jp

トライ中ですがDPの組み方に悩んでいます。
後日の検討のためWAしたコードをあげておきます。

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

int main(){
  int N,K;
  cin>>N>>K;
  
  //DPテーブルの設定と初期化
  long long dp[110][3];
  for(int i=0;i<N;i++){
    for(int j=0;j<3;j++){
      dp[i][j]=0;
    }
  }
  
  //既決分の入力
  int a,b;
  for(int i=0;i<K;i++){
    cin>>a>>b;
    a--;
    b--;
    dp[a][(b+1)%3]=-1;
    dp[a][(b+2)%3]=-1;
  }
  
  for(int i=0;i<3;i++){
    if(dp[N-1][i] == 0){
    dp[N-1][i]=1;
    }
  }
  for(int i=0;i<3;i++){
    if(dp[N-2][i] == 0){
    dp[N-2][i]=1;
    }
  }    
  for(int i=N-3;i>=0;i--){
    for(int j=0;j<3;j++){
      for(int k=0;k<3;k++){
        for(int l=0;l<3;l++){
          if(j==k && k==l) continue;
          if(dp[i][j]==-1||dp[i+1][k]==-1||dp[i+2][l]==-1) continue;
          dp[i][j]+=dp[i+1][k]*dp[i+2][l];
          dp[i][j]%=10000;
        }
      }
    }
  }
  
  for(int i=0;i<N;i++){  
  /*cout<<dp[i][0]<<" "<<dp[i][1]<<" "<<dp[i][2]<<endl;
  }*/
  return 0;
}