Problem:


Score : 800 points

Problem Statement

There are N squares arranged in a row.
The squares are numbered 1, 2, ..., N, from left to right.

Snuke is painting each square in red, green or blue.
According to his aesthetic sense, the following M conditions must all be satisfied.
The i-th condition is:

There are exactly x_i different colors among squares l_i, l_i + 1, ..., r_i.

In how many ways can the squares be painted to satisfy all the conditions?
Find the count modulo 10^9+7.

Constraints

1 ≤ N ≤ 300

1 ≤ M ≤ 300

1 ≤ l_i ≤ r_i ≤ N

1 ≤ x_i ≤ 3

Input

Input is given from Standard Input in the following format:

N M
l_1 r_1 x_1
l_2 r_2 x_2
:
l_M r_M x_M

Output

Print the number of ways to paint the squares to satisfy all the conditions, modulo 10^9+7.

Sample Input 1

3 1
1 3 3

Sample Output 1

6

The six ways are:

RGB

RBG

GRB

GBR

BRG

BGR

where R, G and B correspond to red, green and blue squares, respectively.

Sample Input 2

4 2
1 3 1
2 4 2

Sample Output 2

6

The six ways are:

RRRG

RRRB

GGGR

GGGB

BBBR

BBBG

Sample Input 3

1 3
1 1 1
1 1 2
1 1 3

Sample Output 3

0

There are zero ways.

Sample Input 4

8 10
2 6 2
5 5 1
3 5 2
4 7 3
4 4 1
2 3 1
7 7 1
1 5 2
1 7 3
3 4 2

Sample Output 4

108



Sample input:
3 1
1 3 3


Sample output:
6

Submission status: Wrong Answer

Solution code:
from itertools import permutations
n,m = map(int,input().split())
lrx = [list(map(int,input().split())) for i in range(m)]
lrx.sort(key = lambda x:x[1])
mod = 10**9+7
dp = [[[0 for i in range(n+1)] for j in range(n+1)] for k in range(n+1)]
dp[0][0][0] = 1
for l,r,t in lrx:
  if t != 1:
    for g in range(l):
      for b in range(max(1,g)):
        dp[r][g][b] = -1
  if t != 2:
    for g in range(l,r):
      for b in range(l):
        dp[r][g][b] = -1
  if t != 3:
    for g in range(l,r):
      for b in range(l,g):
        dp[r][g][b] = -1

for r in range(n):
  for g in range(max(1,r)):
    for b in range(max(1,g)):
      v = dp[r][g][b]
      if v == -1:
        continue
      if dp[r+1][g][b] >= 0:
        dp[r+1][g][b] += v
        dp[r+1][g][b] %= mod
      if dp[r+1][r][b] >= 0:
        dp[r+1][r][b] += v
        dp[r+1][r][b] %= mod
      if dp[r+1][g][b] >= 0:
        dp[r+1][g][b] += v
        dp[r+1][g][b] %= mod
ans = 0
for i in range(n):
  for j in range(max(1,i)):
    if dp[n][i][j] >= 0:
      ans += dp[n][i][j]
      ans %= mod
print(ans*6%mod)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
n,m = map(int,input().split())
lrx = [list(map(int,input().split())) for i in range(m)]
lrx.sort(key = lambda x:x[1])
mod = 10**9+7
dp = [[[0 for i in range(n+1)] for j in range(n+1)] for k in range(n+1)]
dp[0][0][0] = 1
for l,r,t in lrx:
  if t != 1:
    for g in range(l):
      for b in range(max(1,g)):
        dp[r][g][b] = -1
  if t != 2:
    for g in range(l,r):
      for b in range(l):
        dp[r][g][b] = -1
  if t != 3:
    for g in range(l,r):
      for b in range(l,g):
        dp[r][g][b] = -1

for r in range(n):
  for g in range(r):
    for b in range(max(1,g)):
      v = dp[r][g][b]
      if v == -1:
        continue
      if dp[r+1][g][b] >= 0:
        dp[r+1][g][b] += v
        dp[r+1][g][b] %= mod
      if dp[r+1][r][b] >= 0:
        dp[r+1][r][b] += v
        dp[r+1][r][b] %= mod
      if dp[r+1][g][b] >= 0:
        dp[r+1][g][b] += v
        dp[r+1][g][b] %= mod
ans = 0
for i in range(n):
  for j in range(max(1,i)):
    if dp[n][i][j] >= 0:
      ans += dp[n][i][j]
      ans %= mod
print(ans*6%mod)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
n,m = map(int,input().split())
lrx = [list(map(int,input().split())) for i in range(m)]
lrx.sort(key = lambda x:x[1])
mod = 10**9+7
dp = [[[0 for i in range(n+1)] for j in range(n+1)] for k in range(n+1)]
dp[0][0][0] = 1
for l,r,t in lrx:
  if t != 1:
    for g in range(l):
      for b in range(max(1,g)):
        for x,y,z in permutations((r,g,b)):
          dp[x][y][z] = -1
  if t != 2:
    for g in range(l,r):
      for b in range(l):
        for x,y,z in permutations((r,g,b)):
          dp[x][y][z] = -1
  if t != 3:
    for g in range(l,r):
      for b in range(l,g):
        for x,y,z in permutations((r,g,b)):
          dp[x][y][z] = -1

for r in range(n):
  for g in range(r):
    for b in range(max(1,g)):
      v = dp[r][g][b]
      if v == -1:
        continue
      if dp[r+1][g][b] >= 0:
        dp[r+1][g][b] += v
        dp[r+1][g][b] %= mod
      if dp[r][r+1][b] >= 0:
        dp[r][r+1][b] += v
        dp[r][r+1][b] %= mod
      if dp[r][g][r+1] >= 0:
        dp[r][g][r+1] += v
        dp[r][g][r+1] %= mod
ans = 0
for i in range(n):
  for j in range(max(1,i)):
    if dp[n][i][j] >= 0:
      ans += dp[n][i][j]
      ans %= mod
print(ans*6%mod)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
n,m = map(int,input().split())
lrx = [list(map(int,input().split())) for i in range(m)]
lrx.sort(key = lambda x:x[1])
mod = 10**9+7
dp = [[[-1 for i in range(n+1)] for j in range(n+1)] for k in range(n+1)]
dp[0][0][0] = 1
ptr = 0
for r in range(1,n+1):
  while ptr < m and lrx[ptr][1] < r:
    ptr += 1
  for g in range(r):
    for b in range(max(1,g)):
      for x,y,z in permutations((r,g,b)):
        dp[x][y][z] = 0
  while ptr < m and lrx[ptr][1] == r:
    l,_,t = lrx[ptr]
    if t != 1:
      for g in range(l):
        for b in range(max(1,g)):
          for x,y,z in permutations((r,g,b)):
            dp[x][y][z] = -1
    if t != 2:
      for g in range(l,r):
        for b in range(l):
          for x,y,z in permutations((r,g,b)):
            dp[x][y][z] = -1
    if t != 3:
      for g in range(l,r):
        for b in range(l,g):
          for x,y,z in permutations((r,g,b)):
            dp[x][y][z] = -1
    ptr += 1
"""
for r in range(n):
  for g in range(n):
    for b in range(n):
      mx = max(r,g,b)
      v = dp[r][g][b]
      if v == -1:
        continue
      if dp[mx+1][g][b] >= 0:
        dp[mx+1][g][b] += v
        dp[mx+1][g][b] %= mod
      if dp[r][mx+1][b] >= 0:
        dp[r][mx+1][b] += v
        dp[r][mx+1][b] %= mod
      if dp[r][g][mx+1] >= 0:
        dp[r][g][mx+1] += v
        dp[r][g][mx+1] %= mod
ans = 0
for i in range(n):
  for j in range(max(1,i)):
    for x,y,z in permutations((n,i,j)):
      if dp[x][y][z] >= 0:
        ans += dp[x][y][z]
        ans %= mod
print(ans)
"""

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

# 右端を色1として、(色2の末尾、色3の末尾) -> 何通り
# よくわからなくなるので、0番：色3、1番：色2、2番：色1を置いた状態から始める。
# 本来のL,RをL+2,R+2に設定

MOD = 10 ** 9 + 7

N,M = map(int,readline().split())
m = map(int,read().split())
LRX = zip(m,m,m)

R_to_LX = [[] for _ in range(N+3)]
for l,r,x in LRX:
    R_to_LX[r+2].append((l+2,x))

dp = np.zeros((N+3,N+3),np.int64)
dp[1,0] = 1
for r in range(3,N+3):
    # まず、末尾に色を置く
    prev = dp
    dp = np.zeros((N+3,N+3),np.int64)
    # 末尾に色 1
    dp += prev
    # 末尾に色 2
    dp[r-1,:] += prev.sum(axis=0)
    # 末尾に色 3
    dp[r-1,:] += prev.sum(axis=1)
    # 禁止条件を処理
    for l,x in R_to_LX[r]:
        if x == 1:
            dp[l:] = 0
        elif x == 2:
            # 2つはある
            dp[:l] = 0
            # 3つはない
            dp[:,l:] = 0
        else:
            # 3つある
            dp[:,:l] = 0
    dp %= MOD

answer = dp.sum()
print(answer)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

# 一番後ろの色を(赤に)固定した上で、もらうDPに書き換え
def main():
    md = 10 ** 9 + 7
    n, m = MI()
    rtol = defaultdict(list)
    for _ in range(m):
        l, r, x = MI()
        rtol[r].append([l, x])
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    for k in range(1, n + 1):
        for i in range(k - 1):
            dp[i][k - 1] = dp[k - 1][i] = sum(dp[i][:k - 1])
        for l, x in rtol[k]:
            if x == 1:
                for i in range(l, k):
                    for j in range(k):
                        dp[i][j] = dp[j][i] = 0
            if x == 2:
                for i in range(l, k):
                    for j in range(i + 1, k):
                        dp[i][j] = dp[j][i] = 0
                for i in range(l):
                    for j in range(i + 1):
                        dp[i][j] = dp[j][i] = 0
            if x == 3:
                for i in range(l):
                    for j in range(k):
                        dp[i][j] = dp[j][i] = 0

    # p2D(dp)
    print(sum(sum(dr) for dr in dp) * 3)

main()

Submission status: Wrong Answer

Solution code:
import itertools
import os
import sys
from functools import lru_cache

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, M = list(map(int, sys.stdin.readline().split()))
L, R, X = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(M)]))

MOD = 10 ** 9 + 7


def ModInt(mod):
    class _ModInt:
        def __init__(self, value):
            self.value = value % mod

        def __add__(self, other):
            if isinstance(other, _ModInt):
                return _ModInt(self.value + other.value)
            else:
                return _ModInt(self.value + other)

        def __radd__(self, other):
            return self.__add__(other)

        def __mul__(self, other):
            if isinstance(other, _ModInt):
                return _ModInt(self.value * other.value)
            else:
                return _ModInt(self.value * other)

        def __repr__(self):
            return str(self.value)

    return _ModInt


# k からどこまで 1 を超えてはいけない？
l1 = np.zeros(N + 1) - 1
# k からどこまで 2 を超えてはいけない？
l2 = np.zeros(N + 1) - 1
# k からどこまでに 2 にならないといけない？
r2 = np.zeros(N + 1) - 1
# k からどこまでに 3 にならないといけない？
r3 = np.zeros(N + 1) - 1
for l, r, x in zip(L, R, X):
    if x == 1:
        l1[l:r + 1] = l
    elif x == 2:
        l2[l:r + 1] = l
        r2[r] = l
    elif x == 3:
        r3[r] = l


@lru_cache(maxsize=10 ** 6)
def ok(a, b, k):
    a, b = min(a, b), max(a, b)
    ret = True
    if l1[k] >= 0:
        ret &= b < l1[k]
    if l2[k] >= 0:
        ret &= a < l2[k]
    if r2[k] >= 0:
        ret &= r2[k] <= b
    if r3[k] >= 0:
        ret &= r3[k] <= a
    return ret


MI = ModInt(mod=MOD)

# dp[r][g][b]: 最後に赤で塗ったインデックスが r、緑が g、青が b のときの総数
dp = [[[0 for _ in range(N + 1)] for _ in range(N + 1)] for _ in range(N + 1)]
if ok(0, 0, 1):
    dp[1][0][0] = MI(1)
    dp[0][1][0] = MI(1)
    dp[0][0][1] = MI(1)
for k in range(1, N + 1):
    r = k - 1
    for g, b in itertools.product(range(k), repeat=2):
        if ok(g, b, k):
            dp[k][g][b] += dp[r][g][b]
        if ok(r, b, k):
            dp[r][k][b] += dp[r][g][b]
        if ok(r, g, k):
            dp[r][g][k] += dp[r][g][b]
    g = k - 1
    for r, b in itertools.product(range(k), repeat=2):
        if ok(g, b, k):
            dp[k][g][b] += dp[r][g][b]
        if ok(r, b, k):
            dp[r][k][b] += dp[r][g][b]
        if ok(r, g, k):
            dp[r][g][k] += dp[r][g][b]
    b = k - 1
    for r, g in itertools.product(range(k), repeat=2):
        if ok(g, b, k):
            dp[k][g][b] += dp[r][g][b]
        if ok(r, b, k):
            dp[r][k][b] += dp[r][g][b]
        if ok(r, g, k):
            dp[r][g][k] += dp[r][g][b]

dp = np.array(dp)
print(dp[-1, :, :].sum() * 3)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
Q=[[int(i) for i in input().split()] for i in range(M)]
Q.sort(key=lambda x:x[1])
mod=10**9+7
dp=[[[0]*max(1,c) for c in range(max(1,b+1))] for b in range(N+1)]
dp[0][0][0]=1
k=0
for a in range(N+1):
  check=[]
  if k<=M-1:
    while a==Q[k][1]:
      l,r,x=Q[k]
      check.append((l,r,x))
      k+=1
      if k==M:
        break
  for b in range(max(1,a)):
    for c in range(max(1,b)):
      for l,r,x in check:
        if x==1:
          if not b<l:
            dp[a][b][c]=0
            continue
        elif x==2:
          if not (b>=l and c<l):
            dp[a][b][c]=0
            continue
        elif x==3:
          if not c>=l:
            dp[a][b][c]=0
            continue
      dp[a][b][c]%=mod
      if a<=N-1:
        dp[a+1][b][c]+=dp[a][b][c]
        dp[a+1][a][c]+=dp[a][b][c]
        dp[a+1][a][b]+=dp[a][b][c]
ans=0
for b in range(N):
  for c in range(b):
    ans+=dp[N][b][c]
    ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
Q=[[int(i) for i in input().split()] for i in range(M)]
Q.sort(key=lambda x:x[1])
mod=10**9+7
dp=[[[0]*(N+1) for i in range(N+1)] for i in range(N+1)]
dp[0][0][0]=1
k=0
for a in range(N+1):
  check=[]
  if k<=M-1:
    while a==Q[k][1]:
      l,r,x=Q[k]
      check.append((l,r,x))
      k+=1
      if k==M:
        break
  for b in range(max(1,a)):
    for c in range(max(1,b)):
      for l,r,x in check:
        if x==1:
          if not b<l:
            dp[a][b][c]=0
            continue
        elif x==2:
          if not (b>=l and c<l):
            dp[a][b][c]=0
            continue
        elif x==3:
          if not c>=l:
            dp[a][b][c]=0
            continue
      dp[a][b][c]%=mod
      if a<=N-1:
        dp[a+1][b][c]+=dp[a][b][c]
        dp[a+1][a][c]+=dp[a][b][c]
        dp[a+1][a][b]+=dp[a][b][c]
ans=0
for b in range(N):
  for c in range(b):
    ans+=dp[N][b][c]
    ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
# seishin.py
from collections import deque
N, M = map(int, input().split())
r_min = [0]*(N+1); r_max = [N+1]*(N+1)
g_min = [0]*(N+1); g_max = [N+1]*(N+1)
Q = [list(map(int, input().split())) for i in range(M)]
rmv = set()
for i in range(M):
    l0, r0, x0 = Q[i]
    for j in range(M):
        l1, r1, x1 = Q[j]
        if i != j and x0 == x1 == 3 and l0 <= l1 and r1 <= r0:
            rmv.add(i)
            break

free = [1]*(N+1)
for i in range(M):
    #l, r, x = map(int, input().split())
    if i in rmv:
        continue
    l, r, x = Q[i]

    # 仮定: R < G < B を元に各r,gの値の範囲を絞り込む(B = rになるため計算しない)
    if x == 1:
        # x = 1の時、あるrに紐づく全てのl_iについて G < l_i を満たす必要がある
        # => G < min(l_i) を満たせばよい
        g_max[r] = min(g_max[r], l-1)
    elif x == 2:
        # x = 2の時、あるrに紐づく全てのl_iについて R < l_i, l_i <= G を満たす必要がある
        # => R < min(l_i), max(l_i) <= G を満たせばよい
        g_min[r] = max(g_min[r], l)
        r_max[r] = min(r_max[r], l-1)
    elif x == 3:
        # x = 3の時、あるrに紐づく全てのl_iについて l_i <= R を満たす必要がある
        # =>  max(l_i) <= R を満たせばよい
        r_min[r] = max(r_min[r], l)

        # r-1の時に満たすべき条件
        g_min[r-1] = max(g_min[r-1], l)

    for j in range(l, r+1):
        free[j] = 0
# rより小さいインデックスで制約が満たすべき条件を伝播して高速化
for r in range(N-1, -1, -1):
    r_max[r] = min(r_max[r], r_max[r+1])
    g_max[r] = min(g_max[r], g_max[r+1])

def check(k, r, g, b):
    return (r_min[k] <= r <= r_max[k] and g_min[k] <= g <= g_max[k])

MOD = 10**9 + 7

# 左からk個置いた時、各色の最右の位置を持ってメモ化dfs
# r < g < b を維持して計算していく
memo = {}
def dfs(k, r, g, b):
    key = r, g, b
    if key in memo:
        return memo[key]
    if not check(k, r, g, b):
        # 制約を満たさない場合 => 0通り
        memo[key] = 0
        return 0
    if k == N:
        memo[key] = 1
        return 1
    if free[k]:
        # N = 300, M = 0の場合等だと制約が少なすぎて定数が落ちない
        # => 制約が疎である場合は、制約がかかってない部分で切って高速化
        res = memo[key] = (3 * dfs(k+1, k, k, k+1)) % MOD
    else:
        # r < g < b < k+1 なので、この関係を元に次のdfs()を計算
        res = memo[key] = (dfs(k+1, g, b, k+1) + dfs(k+1, r, b, k+1) + dfs(k+1, r, g, k+1)) % MOD
    return res
print(dfs(0, 0, 0, 0))

Submission status: Wrong Answer

Solution code:
# seishin.py
from collections import deque
N, M = map(int, input().split())
C = [[] for i in range(N+1)]
for i in range(M):
    l, r, x = map(int, input().split())
    C[r].append((l, x))
dp = [[[0]*N for i in range(N)] for j in range(N)]

def check(k, *L):
    # r < g < b として扱う
    r, g, b = sorted(L)
    for l, x in C[k]:
        # 区間[l, k]内はx種類の色
        if x == 1:
            if not g < l:
                return 0
        elif x == 2:
            if not r < l or not l <= g:
                return 0
        else:
            if not l <= r:
                return 0
    return 1

MOD = 10**18

memo = {}
def dfs(k, r, g, b):
    key = r, g, b
    if key in memo:
        return memo[key]
    if not check(k, r, g, b):
        # 制約を満たさない場合 => 0通り
        memo[key] = 0
        return 0
    if k == N:
        memo[key] = 1
        return 1
    res = memo[key] = (dfs(k+1, k+1, g, b) + dfs(k+1, r, k+1, b) + dfs(k+1, r, g, k+1)) % MOD
    return res
print(dfs(0, 0, 0, 0))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import numpy as np

MOD = 1000000007
iist = lambda: map(int,input().split())

N,M = iist()
Q = defaultdict(list)
for i in range(M):
  l,r,x = iist()
  Q[r].append((l,x-1))

if any(x != 0 for l,x in Q[1]):
  print(0)
  exit(0)

dp = np.zeros((N,N), dtype='i8')
dp[0,0] = 3
memo = np.zeros(N, dtype='i8')
memo[0] = 6
s = 3

for pk in range(1,N):
  k = pk+1
  dp[:,pk] = memo
  memo *= 2
  memo %= MOD

  memo[pk] = 2*s%MOD
  s = 3*s%MOD
  subQ = Q[k]

  for i,j in zip(*np.nonzero(dp[:pk,:k])):
    for l,x in subQ:
      if x != int(l<=i)+int(l<=j):
        c = dp[i,j]
        memo[i] -= c
        memo[j] -= c
        s -= c
        dp[i,j] = 0
        break
  s %= MOD

print(s)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import numpy as np

MOD = 1000000007
iist = lambda: map(int,input().split())

N,M = iist()
Q = defaultdict(list)
for i in range(M):
  l,r,x = iist()
  Q[r].append((l,x-1))

if any(x != 0 for l,x in Q[1]):
  print(0)
  exit(0)

dp = np.zeros((N,N), dtype='i8')
dp[0,0] = 3
memo = np.zeros(N, dtype='i8')
memo[0] = 6
s = 3

for pk in range(1,N):
  k = pk+1
  dp[:pk,pk] = memo[:pk]
  memo[:pk] *= 2
  memo[:pk] %= MOD

  memo[pk] = 2*s%MOD
  s = 3*s%MOD
  subQ = Q[k]

  for i,j in zip(*np.nonzero(dp[:pk,:k])):
    for l,x in subQ:
      if x != int(l<=i)+int(l<=j):
        c = dp[i,j]
        memo[i] -= c
        memo[j] -= c
        s -= c
        dp[i,j] = 0
        break
  s %= MOD

print(s)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import numpy as np

MOD = 1000000007
iist = lambda: map(int,input().split())

N,M = iist()
Q = defaultdict(list)
for i in range(M):
  l,r,x = iist()
  Q[r].append((l,x-1))

if any(x != 0 for l,x in Q[1]):
  print(0)
  exit(0)

dp = np.zeros((N,N), dtype='i4')
dp[0,0] = 3
memo = np.zeros(N, dtype='i4')
memo[0] = 6
s = 3

for pk in range(1,N):
  k = pk+1
  dp[:pk,pk] = memo[:pk]
  memo[:pk] *= 2
  memo[:pk] %= MOD

  memo[pk] = 2*s%MOD
  s = 3*s%MOD
  subQ = Q[k]

  for i,j in zip(*np.nonzero(dp[:pk,:k])):
    for l,x in subQ:
      if x != int(l<=i)+int(l<=j):
        c = dp[i,j]
        memo[i] -= c
        memo[j] -= c
        s -= c
        dp[i,j] = 0
        break
  s %= MOD

print(s)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

MOD = 1000000007
iist = lambda: map(int,input().split())

N,M = iist()
Q = defaultdict(list)
for i in range(M):
  l,r,x = iist()
  Q[r].append((l,x-1))

if any(x != 1 for l,x in Q[1]):
  print(0)
  exit(0)

dp = defaultdict(int)
dp[0,0] = 3

x_sum = [3]
y_sum = [3]
s = 3

for pk in range(1,N):
  k = pk+1

  for i,c in enumerate(map(sum,zip(x_sum,y_sum))):
    c %= MOD
    dp[i,pk] = c
    x_sum[i] += c

  x_sum.append(0)
  y_sum.append(2*s%MOD)
  s = 3*s%MOD
  subQ = Q[k]

  for i,j in list(dp.keys()):
    for l,x in subQ:
      if x != (l<=i)+(l<=j):
        c = dp[i,j]
        x_sum[i] -= c
        y_sum[j] -= c
        y_sum[j] %= MOD
        s -= c
        del dp[i,j]
        break

  for i in range(pk):
    x_sum[i] %= MOD
  s %= MOD

print(s)

Submission status: Time Limit Exceeded

Solution code:

"""

https://atcoder.jp/contests/arc074/tasks/arc074_c

ad-hocに解けるはず
数字が小さい区間に大きい区間が含まれていたら0
まず、1の区間は1色のみ(当たり前)
3の区間は全ての色

dpだとして、どんな状態がまとめれれる？
dp[i][B][G] = i番目まで見て,青がB個,緑がG個の場合の数
→複数ある条件の対処ができない

ではどうやって…？
R,G,Bの個数を管理?
区間の中にある数のΔをr,g,bで表す

1種類→ r*g + r*b + g*b = 0
2種類→ 上を満たさないかつ r*g*b = 0
3種類→ 上を満たさない

======少し答えを見た=====

一番右にある色のindexを管理する？
dp[r][g][b]
更新はr,g,bのどれかを変更する

条件に合わないのを切り捨てるには、
1 → r,g,bで2番目に大きいのがl-1以下を0にする
など分かるはず

更新にかかる計算回数は…？
一つはi-1なのがわかってる
更新の際見るべきは300*300*3
条件が存在しない時を考えよう
O(N^3)で行けるはず

条件による切り捨てを考える
M回切り捨てる、条件を見るのは最大のやつ以外の2つなので O(M * N**2)
結論として O(N^3+MN^2)で解ける

"""

from sys import stdin
import sys

N,M = map(int,stdin.readline().split())
lx = [ [] for i in range(N+1) ]

for i in range(M):

    l,r,x = map(int,stdin.readline().split())
    lx[r].append( (l,x) )

dp = [[[0] * (N+1) for i in range(N+1) ] for j in range(N+1)]
dp[0][0][0] = 1
mod = 10**9+7

for i in range(1,N+1):

    #last is R
    for g in range(i):
        for b in range(i):
            dp[i][g][b] += dp[i-1][g][b]
            dp[i][g][b] %= mod
            dp[i-1][i][b] += dp[i-1][g][b]
            dp[i-1][i][b] %= mod
            dp[i-1][g][i] += dp[i-1][g][b]
            dp[i-1][g][i] %= mod
    #last is G
    for r in range(i):
        for b in range(i):
            dp[i][i-1][b] += dp[r][i-1][b]
            dp[i][i-1][b] %= mod
            dp[r][i][b] += dp[r][i-1][b]
            dp[r][i][b] %= mod
            dp[r][i-1][i] += dp[r][i-1][b]
            dp[r][i-1][i] %= mod

    #last is R
    for r in range(i):
        for g in range(i):
            dp[i][g][i-1] += dp[r][g][i-1]
            dp[i][g][i-1] %= mod
            dp[r][i][i-1] += dp[r][g][i-1]
            dp[r][i][i-1] %= mod
            dp[r][g][i] += dp[r][g][i-1]
            dp[r][g][i] %= mod

    #remove
    for l,x in lx[i]:
        if x == 1: #iで無い添え字が以上のものを全部0にする
            #R is i
            for g in range(i):
                for b in range(i):
                    if g >= l or b >= l:
                        dp[i][g][b] = 0
            #G is i
            for r in range(i):
                for b in range(i):
                    if r >= l or b >= l:
                        dp[r][i][b] = 0
            #B is l
            for r in range(i):
                for g in range(i):
                    if r >= l or g >= l:
                        dp[r][g][i] = 0

        elif x == 2: #iでない添え字のうち片方がl以上かつもう片方がl未満でないものを0にする
            for g in range(i):
                for b in range(i):
                    if not (g >= l > b or b >= l > g):
                        dp[i][g][b] = 0
            #G is i
            for r in range(i):
                for b in range(i):
                    if not (r >= l > b or b >= l > r):
                        dp[r][i][b] = 0
            #B is l
            for r in range(i):
                for g in range(i):
                    if not (r >= l > g or g >= l > r):
                        dp[r][g][i] = 0

        else: #どれかの添え字がl未満のものを0にする
            #R is i
            for g in range(i):
                for b in range(i):
                    if g < l or b < l:
                        dp[i][g][b] = 0
            #G is i
            for r in range(i):
                for b in range(i):
                    if r < l or b < l:
                        dp[r][i][b] = 0
            #B is l
            for r in range(i):
                for g in range(i):
                    if r < l or g < l:
                        dp[r][g][i] = 0

ans = 0
#print (dp)
for i in range(N):
    for j in range(N):
        ans += dp[N][i][j] # + dp[i][N][j] + dp[i][j][N]
        ans%= mod
print (ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

mod = 10**9+7

N, M = map(int, input().split())
LRX = [list(map(int, input().split())) for _ in range(M)]

LX = [[] for _ in range(N+2)]
for l, r, x in LRX:
    LX[r].append((l, x))

dp = [[[0]*(N+2) for _ in range(N+2)] for _ in range(N+2)]
# dp[i][j][k] (i <= j <= k) 
# 三色それぞれ、最後に使ったindex(1-indexed)がi,j,k

dp[0][0][0] = 1

# (i, j, k+1)に置くのが、条件(l,x)に適しているか
def check(i, j, l, x):
    return (x == 3 and l <= i) or (x == 2 and i < l <= j) or (x == 1 and j < l)

for i in range(N+1):
    for j in range(i, N+1):
        for k in range(j, N+1):
            
            # 一番前の色を置く
            ok = True
            for l, x in LX[k+1]:
                if not check(j, k, l, x):
                    ok = False
            if ok:
                dp[j][k][k+1] = (dp[j][k][k+1] + dp[i][j][k]) % mod
            
            # 最後
            ok = True
            for l, x in LX[k+1]:
                if not check(i, j, l, x):
                    ok = False
            if ok:
                dp[i][j][k+1] = (dp[i][j][k+1] + dp[i][j][k]) % mod
            
            # 二番目
            ok = True
            for l, x in LX[k+1]:
                if not check(i, k, l, x):
                    ok = False
            if ok:
                dp[i][k][k+1] = (dp[i][k][k+1] + dp[i][j][k]) % mod
        

                

ans = 0
for a in range(N+1):
    for b in range(N+1):
        ans = (ans + dp[a][b][N]) % mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
n, m = map(int, input().split())
q = [[] for _ in range(n+1)]
for _ in range(m):
	l, r, x = map(int, input().split())
	q[r].append((l, x))

dp = [[[0 for _ in range(n+1)] for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0] = 1

cum = [[0 for _ in range(n+1)] for _ in range(n+1)]

for r in range(1, n+1):
	for g in range(r):
		for b in range(r):
			if g+b > 0 and b >= g:
				continue
			dp[r][g][b] = dp[r-1][g][b]
			if g == r-1 or b == r-1:
				dp[r][g][b] += cum[g][b]
				dp[r][g][b] %= MOD
			for l, x in q[r]:
				if x == 1:
					if g >= l or b >= l:
						dp[r][g][b] = 0
				if x == 2:
					if (g >= l and b >= l) or (g < l and b < l):
						dp[r][g][b] = 0
				if x == 3:
					if g < l or b < l:
						dp[r][g][b] = 0
			cum[g][b] += dp[r][g][b]
			cum[g][b] %= MOD
			#print(r, g, b, dp[r][g][b])
			if g+b > 0:
				dp[r][b][g] = dp[r][g][b]
				cum[b][g] += dp[r][g][b]
				cum[b][g] %= MOD
				dp[b][r][g] = dp[r][g][b]
				cum[r][g] += dp[r][g][b]
				cum[r][g] %= MOD
				dp[b][g][r] = dp[r][g][b]
				cum[g][r] += dp[r][g][b]
				cum[g][r] %= MOD
				dp[g][r][b] = dp[r][g][b]
				cum[r][b] += dp[r][g][b]
				cum[r][b] %= MOD
				dp[g][b][r] = dp[r][g][b]
				cum[b][r] += dp[r][g][b]
				cum[b][r] %= MOD
			else:
				dp[0][r][0] = dp[r][0][0]
				dp[0][0][r] = dp[r][0][0]
				cum[r][0] += dp[r][0][0]
				cum[r][0] %= MOD
				cum[0][r] += dp[r][0][0]
				cum[0][r] %= MOD

ans = (3 * dp[n][0][0]) % MOD
for i in range(n):
	for j in range(i):
		ans += 6 * dp[n][i][j]
		ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
l,r,x=0,0,0
Q=[[] for i in range(N+1)]
for i in range(M):
  l,r,x=map(int,input().split())
  Q[r].append((l,x))
DP=[[[0]*(N+2) for i in range(N+2)] for j in range(N+2)]
DP[0][0][0]=1
mod=10**9+7
k,c=0,0
for z in range(N+1):
  for r in range(z+1):
    for g in range(z+1):
      for b in range(z+1):
        if max(r,g,b)!=z:
          continue
        for i in range(len(Q[z])):
          c=0
          if Q[z][i][0]<=r:
            c+=1
          if Q[z][i][0]<=g:
            c+=1
          if Q[z][i][0]<=b:
            c+=1
          if c!=Q[z][i][1]:
            DP[r][g][b]=0
        DP[z+1][g][b]=(DP[z+1][g][b]+DP[r][g][b])%mod
        DP[r][z+1][b]=(DP[r][z+1][b]+DP[r][g][b])%mod
        DP[r][g][z+1]=(DP[r][g][z+1]+DP[r][g][b])%mod
P=0
for i in range(N+1):
  for j in range(N+1):
    for k in range(N+1):
      if max(i,j,k)==N:
        P=(P+DP[i][j][k])%mod
print(P)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
q=[[] for i in range(N+1)]
for i in range(M):
    l,r,x=map(int,input().split())
    q[r].append((l,x))
mod=10**9+7

dp=[[0 for i in range(N+1)] for i in range(N+1)]

i=N
for j in range(N+1):
    for k in range(N+1):
        check=7
        for l,x in q[i]:
            if x==1:
                if i-1>=l>j:
                    check&=1
                elif i==l:
                    check&=7
                else:
                    check=0
            elif x==2:
                if i==l:
                    check=0
                elif i-1>=l>j:
                    check&=6
                elif j>=l>k:
                    check&=3
                else:
                    check=0
            else:
                if i==l:
                    check=0
                elif i-1>=l>j:
                    check=0
                elif j>=l>k:
                    check&=4
        dp[j][k]=bin(check).count("1")

ndp=[[0 for j in range(N+1)] for k in range(N+1)]
s=[(j,k) for j in range(N+1) for k in range(N+1)]
for i in range(N-1,0,-1):
    for j,k in s:
        check=7
        for l,x in q[i]:
            if i==l:
                check=(x==1)*check
            elif i-1>=l>j:
                check=(x==1)*(check%2)+(x==2)*(check&6)
            elif j>=l>k:
                check=(x==2)*(check&3)+(x==3)*(check&4)
            else:
                check*=(x==3)
            
        ndp[j][k]=(dp[j][k]*((check//1)%2)+dp[i-1][k]*((check//2)%2)+dp[i-1][j]*((check//4)%2))%mod
    dp=ndp

print(dp[0][0])

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
q=[[] for i in range(N+1)]
for i in range(M):
    l,r,x=map(int,input().split())
    q[r].append((l,x))
mod=10**9+7

dp=[[0 for i in range(N+1)] for i in range(N+1)]

i=N
for j in range(N+1):
    for k in range(N+1):
        check=7
        for l,x in q[i]:
            if x==1:
                if i-1>=l>j:
                    check&=1
                elif i==l:
                    check&=7
                else:
                    check=0
            elif x==2:
                if i==l:
                    check=0
                elif i-1>=l>j:
                    check&=6
                elif j>=l>k:
                    check&=3
                else:
                    check=0
            else:
                if i==l:
                    check=0
                elif i-1>=l>j:
                    check=0
                elif j>=l>k:
                    check&=4
        dp[j][k]=bin(check).count("1")

ndp=[[0 for j in range(N+1)] for k in range(N+1)]
for i in range(N-1,0,-1):
    for j in range(N+1):
        for k in range(N+1):
            t=0
            check=7
            for l,x in q[i]:
                if x==1:
                    if i-1>=l>j:
                        check&=1
                    elif i==l:
                        check&=7
                    else:
                        check=0
                elif x==2:
                    if i==l:
                        check=0
                    elif i-1>=l>j:
                        check&=6
                    elif j>=l>k:
                        check&=3
                    else:
                        check=0
                else:
                    if i==l:
                        check=0
                    elif i-1>=l>j:
                        check=0
                    elif j>=l>k:
                        check&=4
            t=dp[j][k]*((check//1)%2)+dp[i-1][k]*((check//2)%2)+dp[i-1][j]*((check//4)%2)
            t%=mod
            ndp[j][k]=t
    dp=ndp

print(dp[0][0])