Problem:


Score : 300 points

Problem Statement

Given are positive integers N, M, Q, and Q quadruples of integers ( a_i , b_i , c_i , d_i ).

Consider a sequence A satisfying the following conditions:

A is a sequence of N positive integers.

1 \leq A_1 \leq A_2 \le \cdots \leq A_N \leq M.

Let us define a score of this sequence as follows:

The score is the sum of d_i over all indices i such that A_{b_i} - A_{a_i} = c_i. (If there is no such i, the score is 0.)

Find the maximum possible score of A.

Constraints

All values in input are integers.

2 ≤ N ≤ 10

1 \leq M \leq 10

1 \leq Q \leq 50

1 \leq a_i < b_i \leq N ( i = 1, 2, ..., Q )

0 \leq c_i \leq M - 1 ( i = 1, 2, ..., Q )

(a_i, b_i, c_i) \neq (a_j, b_j, c_j) (where i \neq j)

1 \leq d_i \leq 10^5 ( i = 1, 2, ..., Q )

Input

Input is given from Standard Input in the following format:

N M Q
a_1 b_1 c_1 d_1
:
a_Q b_Q c_Q d_Q

Output

Print the maximum possible score of A.

Sample Input 1

3 4 3
1 3 3 100
1 2 2 10
2 3 2 10

Sample Output 1

110

When A = \{1, 3, 4\}, its score is 110. Under these conditions, no sequence has a score greater than 110, so the answer is 110.

Sample Input 2

4 6 10
2 4 1 86568
1 4 0 90629
2 3 0 90310
3 4 1 29211
3 4 3 78537
3 4 2 8580
1 2 1 96263
1 4 2 2156
1 2 0 94325
1 4 3 94328

Sample Output 2

357500

Sample Input 3

10 10 1
1 10 9 1

Sample Output 3

1



Sample input:
3 4 3
1 3 3 100
1 2 2 10
2 3 2 10


Sample output:
110

Submission status: Wrong Answer

Solution code:
N,M,Q = (int(x) for x in input().split())
ABCD  = [0]*Q
for T in range(0,Q):
    ABCD[T] = [int(x) for x in input().split()]
    
MaxP  = 0
for A1 in range(0,M+1):
    for A2 in range(A1,M+1):
        if N<=2:
            Point = 0
            A = [A1,A2]
            for TT in range(0,Q):
                if A[ABCD[TT][1]-1]-A[ABCD[TT][0]-1]==ABCD[TT][2]:
                    Point = Point + ABCD[TT][3]
            if Point > MaxP:
                MaxP = Point
        else:
            for A3 in range(A2,M+1):
                if N<=3:
                    Point = 0
                    A = [A1,A2,A3]
                    for TT in range(0,Q):
                        if A[ABCD[TT][1]-1]-A[ABCD[TT][0]-1]==ABCD[TT][2]:
                            Point = Point + ABCD[TT][3]
                    if Point > MaxP:
                        MaxP = Point                    
                else:
                    for A4 in range(A3,M+1):
                        if N<=4:
                            Point = 0
                            A = [A1,A2,A3,A4]
                            for TT in range(0,Q):
                                if A[ABCD[TT][1]-1]-A[ABCD[TT][0]-1]==ABCD[TT][2]:
                                    Point = Point + ABCD[TT][3]
                            if Point > MaxP:
                                MaxP = Point
                        else:
                            for A5 in range(A4,M+1):
                                if N<=5:
                                    Point = 0
                                    A = [A1,A2,A3,A4,A5]
                                    for TT in range(0,Q):
                                        if A[ABCD[TT][1]-1]-A[ABCD[TT][0]-1]==ABCD[TT][2]:
                                            Point = Point + ABCD[TT][3]
                                    if Point > MaxP:
                                        MaxP = Point                                    
                                else:
                                    for A6 in range(A5,M+1):
                                        if N<=6:
                                            Point = 0
                                            A = [A1,A2,A3,A4,A5,A6]
                                            for TT in range(0,Q):
                                                if A[ABCD[TT][1]-1]-A[ABCD[TT][0]-1]==ABCD[TT][2]:
                                                    Point = Point + ABCD[TT][3]
                                            if Point > MaxP:
                                                MaxP = Point                                        
                                        else:
                                            for A7 in range(A6,M+1):
                                                if N<=7:
                                                    Point = 0
                                                    A = [A1,A2,A3,A4,A5,A6,A7]
                                                    for TT in range(0,Q):
                                                        if A[ABCD[TT][1]-1]-A[ABCD[TT][0]-1]==ABCD[TT][2]:
                                                            Point = Point + ABCD[TT][3]
                                                    if Point > MaxP:
                                                        MaxP = Point                                                
                                                else:
                                                    for A8 in range(A7,M+1):
                                                        if N<=8:
                                                            Point = 0
                                                            A = [A1,A2,A3,A4,A5,A6,A7,A8]
                                                            for TT in range(0,Q):
                                                                if A[ABCD[TT][1]-1]-A[ABCD[TT][0]-1]==ABCD[TT][2]:
                                                                    Point = Point + ABCD[TT][3]
                                                            if Point > MaxP:
                                                                MaxP = Point                                                            
                                                        else:
                                                            for A9 in range(A8,M+1):
                                                                if N<=9:
                                                                    Point = 0
                                                                    A = [A1,A2,A3,A4,A5,A6,A7,A8,A9]
                                                                    for TT in range(0,Q):
                                                                        if A[ABCD[TT][1]-1]-A[ABCD[TT][0]-1]==ABCD[TT][2]:
                                                                            Point = Point + ABCD[TT][3]
                                                                    if Point > MaxP:
                                                                        MaxP = Point                                                                
                                                                else:
                                                                    for A10 in range(A9,M+1):
                                                                        Point = 0
                                                                        A = [A1,A2,A3,A4,A5,A6,A7,A8,A9,A10]
                                                                        for TT in range(0,Q):
                                                                            if A[ABCD[TT][1]-1]-A[ABCD[TT][0]-1]==ABCD[TT][2]:
                                                                                Point = Point + ABCD[TT][3]
                                                                        if Point > MaxP:
                                                                            MaxP = Point
print(MaxP)

Submission status: Wrong Answer

Solution code:
import sys
def basen(x,n):
    if (int(x/n)):return basen(int(x/n),n)+str(x%n)
    return str(x%n)
def f(s,n):
    L=['0']*(n-len(s))+list(s)
    return list(map(lambda x:int(x)+1,L))
def main():
    N,M,Q=tuple(map(int,sys.stdin.readline().split()))
    R,res=[],0
    for _ in [0]*Q:
        a,b,c,d=tuple(map(int,sys.stdin.readline().split()))
        R.append((a-1,b-1,c,d))
    for i in range(M**N):
        A,y=f(basen(i,M),N),0
        for a,b,c,d in R:y=y+d if A[b]-A[a]==c else y
        if res<y:res=y
    print(res)
if __name__=='__main__':main()

Submission status: Wrong Answer

Solution code:
import itertools
n, m, q = list(map(int,input().split()))
sets = [list(map(int,input().split())) for i in range(q)]
print(sets)
mx = 0
nums = list(range(1,m+1))
for h in itertools.combinations_with_replacement(nums,n):
    mxtemp = 0
    for j in range(q):
        a = sets[j][0]
        b = sets[j][1]
        if list(h)[b-1] - list(h)[a-1] == sets[j][2]:
            mxtemp += sets[j][3]
    if mxtemp > mx:
        mx = mxtemp
print(mx)

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
Q_list = []
for i in range(Q):
  Q_list.append(list(map(int, input().split())))


max_cost = 0
#use dfs to find all possible sequences
def dfs(A):
  global max_cost
  #termination condition
  if (len(A)==N):
    cost = 0
    #calculate cost
    for Q in Q_list:
      a = Q[0]
      b = Q[1]
      c = Q[2]
      d = Q[3]
      if (A[b-1]-A[a-1]==c):
        cost += d
    if (cost>max_cost):
      max_cost = cost
    return 1
  #dfs recursion part
  low = 0
  if (A == []):
    low = 1
  else:
  	low = A[-1]
  for i in range(low, M-(N-len(A)-2)):
    dfs(A + [i])
  return 1
dfs([])
print(max_cost)

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
Q_list = []
for i in range(Q):
  Q_list.append(list(map(int, input().split())))


max_cost = 0
#use dfs to find all possible sequences
def dfs(A):
  global max_cost
  #termination condition
  if (len(A)==N):
    cost = 0
    #calculate cost
    for Q in Q_list:
      a = Q[0]
      b = Q[1]
      c = Q[2]
      d = Q[3]
      if (A[b-1]-A[a-1]==c):
        cost += d
    if (cost>max_cost):
      max_cost = cost
    return 1
  #dfs recursion part
  low = 0
  if (A == []):
    low = 1
  else:
  	low = A[-1]
  for i in range(low, M-(N-len(A)-2)):
    dfs(A + [i])
    
dfs([])
print(max_cost)

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
Q_list = []
for i in range(Q):
  Q_list.append(list(map(int, input().split())))


max_cost = 0
#use dfs to find all possible sequences
def dfs(A):
  global max_cost
  #termination condition
  if (len(A)==N):
    cost = 0
    #calculate cost
    for Q in Q_list:
      a = Q[0]
      b = Q[1]
      c = Q[2]
      d = Q[3]
      if (A[b-1]-A[a-1]==c):
        cost += d
    if (cost>max_cost):
      max_cost = cost
    return 1
  #dfs recursion part
  low = 0
  if (A == []):
    low = 1
  else:
  	low = A[-1]+1
  for i in range(low, M-(N-len(A)-2)):
    dfs(A + [i])
    
dfs([])
print(max_cost)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import itertools
import numpy as np
from numba import njit

#入力
readline=stdin.readline
N,M,Q=map(int,readline().split())
a=np.zeros(Q,dtype=np.int64)
b=np.zeros(Q,dtype=np.int64)
c=np.zeros(Q,dtype=np.int64)
d=np.zeros(Q,dtype=np.int64)
for i in range(Q):
    a[i],b[i],c[i],d[i]=map(int,readline().split())

arrays=np.array(list(itertools.combinations_with_replacement(range(1,M+1),N)),dtype=np.int64)
l=len(arrays)

@njit
def f():
    max_res=0
    for i in range(l):
        res=0
        for i in range(Q):
            if arrays[i][b[i]-1]-arrays[i][a[i]-1]==c[i]:
                res+=d[i]
        max_res=max(max_res,res)
    return max_res

print(f())

Submission status: Wrong Answer

Solution code:
#https://atcoder.jp/contests/abc165/submissions/12672182
#写経
import itertools
import numpy as np

def resolve():
    N,M,Q = map(int,input().split())
    A = np.array(list(itertools.combinations_with_replacement(range(1,M+1),N)))
    s = np.zeros(len(A), np.int32)

    for i in range(Q):
        a,b,c,d = map(int,input().split()) 
        s += d * (A[:,b-1] - A[:,a-1] == c)
    print(s.max())

Submission status: Wrong Answer

Solution code:
import itertools
n,m,q = (int(x) for x in input().split())
l = []
a = [1,2,3,4,5,6,7,8,9,10]
b = []
c = []
d = []


for i in range(q):
    l.append([])
    l[i]=list(map(int, input().split()))
    
for i in itertools.combinations_with_replacement(a[:m], r=n):#考えられる数列
        b.append(i) 
print(b)        
    
for i in range(len(b)):#それぞれの数列の得点表
    d.append(0)

for i in range(q):
    w=l[i][0]-1#a
    x=l[i][1]-1#b
    y=l[i][2]#c
    z=l[i][3]#d
    for j in range(len(b)):
        if b[j][x]-b[j][w]==y:
            d[j]+=z

print(max(d))

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int,input().split())
l = []
for _ in range(Q):
    l.append(list(map(int,input().split())))

arr = [1]*N
m = 0

while arr[N-1] < M+1:
    calc = 0
    for i in l:
        if arr[i[1]-1] - arr[i[0]-1] == i[2]:
            calc += i[3]
    if calc > m:
        m = calc
    F = True
    while F:
        arr[0] += 1
        for j in range(N-1):
            if arr[j] > M:
                arr[j] = 0
                arr[j+1] += 1
        for j in range(N-1):
            if arr[j] <= arr[j+1]:
                F =False
            else:
                break

print(m)

Submission status: Wrong Answer

Solution code:
from collections import deque
de = deque()
n,m,q = map(int,input().split())
queries = []
for _ in range(q):
    a,b,c,d = map(int,input().split())
    queries.append((a,b,c,d))
de.append([1])#bfsで作成する数列
maxscore = 0
while de:
    print(de)
    li = de.popleft()
    if len(li) < n:
        for i in range(li[-1],m+1):
            new_li = li + [i]
            de.append(new_li)
    else:
        score = 0
        for i in range(q):
            a,b,c,d = queries[i]
            if li[b-1] - li[a-1] == c:
                score += d
        maxscore = max(maxscore,score)
print(maxscore)

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
abcd = [tuple(map(int, input().split())) for _ in range(Q)]
ans = 0
def calc(p):
    ret = 0
    for a, b, c, d in abcd:
        if p[b] - p[a] == c:
            ret += d
    return ret

def dfs(a, d):
    global ans
    if d == N+1:
        ans = max(ans, calc(a))
        return
    for i in range(a[-1], M+1):
        dfs(a+[i], d+1)

dfs([0], 1)
print(ans)

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())

lst = []
for i in range(Q):
  lst.append(list(map(int, input().split())))
  
  
import itertools

## product 順番あり 重複あり（全て）
## premutations 順番あり 重複なし
## combinations 順番なし　重複なし
## combinations_with_replacement 順番なし　重複あり

A_pattern = itertools.combinations_with_replacement(range(0, M+1), N)
ans = 0

for a in A_pattern:
  point = 0
  
  for l in lst:
    if a[l[1]-1] - a[l[0]-1] == l[2]:
      point += l[3]
      
  if ans < point:
    ans = point
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import combinations_with_replacement as cwr
input = sys.stdin.readline

def dfs(n,m):
    adj = {}
    for i in range(1,m+1):
        adj[i] = [j for j in range(i,m+1)]
    
    stack = [[i] for i in range(1,m+1)]
    combs = []
    while stack:
        node = stack.pop()
        if len(node) == n:
            combs.append(node)
        else:
            for child in adj[node[-1]]:
                cand = node+[child]
                stack.append(cand)
    return combs


N,M,Q = map(int,input().split())
A,B,C,D = [],[],[],[]
for i in range(Q):
    a,b,c,d = map(int,input().split())
    a,b = a-1, b-1
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)

ans = 0
combs = dfs(N,M)
#combs = cwr(range(1,M+1),N)
print(combs)
ans = [0]*(len(combs))
for i,comb in enumerate(combs):
    for a,b,c,d in zip(A,B,C,D):
        if comb[b] - comb[a] ==c:
            ans[i] += d
print(max(ans))

Submission status: Wrong Answer

Solution code:
N,M,Q = map(int,input().split())
h = []
for i in range(Q):
    h.append(list(map(int,input().split())))
A = []
def makelist(n):
    if n == 0:
        return [[]]
    else:
        a = makelist(n-1)
        b = makelist(n-1)
        for i in range(len(a)):
            a[i].append(n)
        return(a+b)
for i in makelist(M):
    if len(i) == N:
        A.append(i)
    else:
        pass
s = 0
SUM = 0
for a in A:
    for i in range(Q):
        if a[h[i][1]-1]-a[h[i][0]-1] == h[i][2]:
            s = s+h[i][3]
        else:
            pass
    if s > SUM:
        SUM = s
    else:
        pass
    s = 0
print(SUM)

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

N, M, Q = map(int, readline().split())

kumi = []
for _ in range(Q):
    tmp = list(map(int, readline().split()))
    kumi.append(tmp)

ans = 0
res = []
def F(l):
    if len(l) == N:
        ans = 0
        for i in range(Q):
            a, b, c, d = kumi[i]
            if l[b-1] - l[a-1] == c:
                ans += d
        yield ans
        return
    for i in range(M):
        l.append(i)
        yield from F(l)
        l.pop()

ans = max(F([]))
print(ans)

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
integer_list = [list(map(int, input().split())) for i in range(Q)]
ans, use_cnt, unuse_cnt = 0, 0, 0
use_num_list = [0]
combi_list = []

def combi(use_num_list):
    for i in range(max(use_num_list), M + 1):
        if N - len(use_num_list) > M - i + 1:
            break
        
        if len(use_num_list) == N:
            combi_list.append(use_num_list[1:] + [i])
            continue
        else:
            combi(use_num_list + [i])

combi(use_num_list)

for cmb in combi_list:
    tmp_ans = 0
    for int_combi in integer_list:
        if cmb[int_combi[1] - 1] - cmb[int_combi[0] - 1] == int_combi[2]:
            tmp_ans += int_combi[3]
    
    ans = max(ans, tmp_ans)

print(ans)

Submission status: Wrong Answer

Solution code:
# 全探索の気持ちが芽生える なにを全探索する？
# Qだと2^50なので無理になる、
# Nをしたいが10^10では？と無理になる
# と思いきや条件からA[i-1]<=A[i]なのでだいぶ減りそうとなる
# 計算量の見積もりがぜんぜんできないがたぶんいけるとなる
from collections import deque
n, m, q = map(int, input().split())
queries = []
for _ in range(q):
    queries.append(tuple(map(int, input().split())))

queue = deque()
for i in range(1, m + 1):
    queue.append([i])

ans = 0


def calc(arr):
    ret = 0
    for a, b, c, d in queries:
        if arr[b - 1] - arr[a - 1] == c:
            ret += d
    return ret


while len(queue) > 0:
    nex_queue = deque()
    for qq in queue:
        if len(qq) == n:
            ans = max(ans, calc(qq))
        else:
            for i in range(qq[0], m + 1):
                nex_qq = qq[:]
                nex_qq.append(i)
                nex_queue.append(nex_qq)
    queue = nex_queue
print(ans)

Submission status: Wrong Answer

Solution code:
def next_array(array):#辞書式に次の配列を与える関数
  s = -1
  for x in array[::-1]:
    if x < M:
      break
    else:
      s -= 1
    #Mより小さい最後の項を取得
  
  if s >= -N:
    array[s] += 1#その項を１増やす
    if s < -1:
      for i in range(s+1,0):#以降の項を全て同じ値に
        array[i] = array[s]
  
  print(array)
  return array
 
def score(array, rules):#点数計算
  scr = 0
  for rule in rules:
    if (array[rule[1]-1] - array[rule[0]-1] == rule[2]):
      scr += rule[3]
      
  return scr
 
# input
N, M, Q = map(int, input().split())
rules = []
 
for i in range(Q):
  a, b, c, d = map(int, input().split())
  rules.append([a, b, c, d])
  
array = [1] * N
max_scr = 0
 
while True:
  max_scr = max(max_scr, score(array,rules)) 
  if array[0] == M:#全探索完了
    break 
  array = next_array(array)#次の配列へ
    
print(max_scr)

Submission status: Wrong Answer

Solution code:
def next_array(array):#辞書式に次の配列を与える関数
  s = -1
  for x in array[::-1]:
    if x < M:
      break
    else:
      s -= 1
    #Mより小さい最後の項を取得
  
  if s >= -N:
    array[s] += 1#その項を１増やす
    if s < -1:
      for i in range(s+1,0):#以降の項を全て同じ値に
        array[i] = array[s]
  
  print(array)
  return array
 
def score(array, rules):#点数計算
  scr = 0
  for rule in rules:
    if (array[rule[1]-1] - array[rule[0]-1] == rule[2]):
      scr += rule[3]
      
  return scr
 
# input
N, M, Q = map(int, input().split())
rules = []

for i in range(Q):
  a, b, c, d = map(int, input().split())
  rules.append([a, b, c, d])

array = [1] * N
max_scr = 0
 
while True:
  max_scr = max(max_scr, score(array,rules)) 
  if array[0] == M:#全探索完了
    break 
  array = next_array(array)#次の配列へ
    
print(max_scr)

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]

q = []
def dp(arg):
    global N
    if len(arg) == N:
        q.append(arg)
    else:
        tmp = 0 if len(arg) == 0 else arg[-1]
        for i in range(tmp, M + 1):
            dp(arg + [i])

dp([])

ans = 0
for A_tmp in q:
    ans_tmp = 0
    for j, (aj, bj, cj, dj) in enumerate(abcd):
        if A_tmp[bj - 1] - A_tmp[aj - 1] == cj:
            ans_tmp += dj
    #
    ans = max(ans, ans_tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N, M, Q = map(int, input().split())
    abcd = [tuple(map(int, input().split())) for _ in range(Q)]
    stk = [[]]
    ans = 0
    while stk:
        A = stk.pop()
        if len(A) < N:
            t = A[-1] if len(A) > 0 else 0
            for i in range(t, 10):
                stk.append(A + [i])
        else:
            t = 0
            for a, b, c, d in abcd:
                if A[b - 1] - A[a - 1] == c:
                    t += d
            ans = max(ans, t)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools

N, M, Q = map(int,input().split())
ls = [list(map(int,input().split())) for i in range(Q)]

Mls = list(range(1,M+1))
Mls = [str(n) for n in Mls]
l = list(itertools.combinations_with_replacement("".join(Mls),N))

ans = 0
for i in l:
    pnt = 0
    for l in ls:
        if int(i[l[1]-1])-int(i[l[0]-1]) == l[2]:
            pnt += l[3]
    ans = max(ans,pnt)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

n, m, q = map(int, input().split())

e = []

for i in range(q):
  e.append(list(map(int, input().split())))

a = itertools.combinations(list(range(m)),n)

max_total = 0

for i in a:
  total = 0
  
  for j in e:
    if i[j[1]-1] - i[j[0]-1] == j[2]:
      total += j[3]
  
  if max_total < total:
    max_total = total
      
print(max_total)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    n,m,q=INTM()
    aq=[]
    for i in range(q):
        aq.append(LIST())
    number = [int(i+1) for i in range(m)]
    
    ans=0
    for i in combinations(number,n):
        temp=0
        for k in aq:
            if i[k[1]-1]-i[k[0]-1]==k[2]:
                temp+=k[3]
        ans=max(ans,temp)
    print(ans)
    
if __name__ == '__main__':
    do()

Submission status: Wrong Answer

Solution code:
import itertools
n,m,q = map(int, input().split())
candidates = [i for i in range(1,m+1)]
a = [0]*q
b = [0]*q
c = [0]*q
d = [0]*q
for i in range(q):
  a[i], b[i], c[i], d[i]  = map(int, input().split())

max_score = 0
for A in itertools.combinations(candidates, n):
  A = list(A)
  score = 0
  for i in range(q):
    if A[b[i]-1] - A[a[i]-1] == c[i]:
      score += d[i]
  max_score = max(max_score, score)
print(max_score)

Submission status: Wrong Answer

Solution code:
def dfs(n, lower):
    if n == N:
        return [[]]
    else:
        res = []
        for i in range(lower, M + 1):
            for p in dfs(n + 1, i):
                res.append([i] + p)
        return res


N, M, Q = map(int, input().split())
A, B, C, D = [], [], [], []
for _ in range(Q):
    a, b, c, d = map(int, input().split())
    A.append(a - 1)
    B.append(b - 1)
    C.append(c)
    D.append(d)
res = 0
for p in dfs(0, 0):
    cur = 0
    for a, b, c, d in zip(A, B, C, D):
        if p[b] - p[a] == c:
            cur += d
    res = max(res, cur)
print(res)

Submission status: Wrong Answer

Solution code:
import itertools
n, m, q = map(int, input().split())

array = []
for i in range(q):
    a = list(map(int, input().split()))
    array.append(a)

comb = list(itertools.combinations(range(1, m+1), n))

ans = 0
for i in comb:
    score = 0
    for a, b, c, d in array:
        if i[b-1] - i[a-1] == c:
            score += d
        ans = max(ans, score)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
n, m, q = map(int, input().split())

array = []
for i in range(q):
    a = list(map(int, input().split()))
    array.append(a)

comb = list(itertools.combinations(range(1, m+1), n))

ans = -1
for i in comb:
    score = 0
    for a, b, c, d in array:
        if i[b-1] - i[a-1] == c:
            score += d
        ans = max(ans, score)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

N, M, Q = map(int , sys.stdin.readline().rstrip().split())
L=[list(map(int, sys.stdin.readline().rstrip().split())) for i in range(Q)]
ans=0
for i in range(1<<M):
	cnt=0
	total=0
	Vals=[]
	for j in range(M):	#choise valueN in 1~M
		if((i>>j)&1):
			cnt+=1
			Vals.append(j+1)
	if cnt==N:
		for l in L:
			if Vals[l[1]-1]-Vals[l[0]-1]==l[2]:total+=l[3]
		if ans<total:ans=total
print(ans)

Submission status: Wrong Answer

Solution code:
n,m,q = map(int, input().split())

sets = [list(map(int, input().split())) for i in range(q)]

score = 0

a = [1] * n

def sco(a):
    scotem = 0
    for i in sets:
        if(a[i[1]-1] - a[i[0]-1] == i[2]):
            scotem += i[3]
    return scotem

flag = 1

while True:
    for i in range(n-1,-1,-1):
        flag = 0
        if(a[i] < m):
            flag = 1
            a[i] = a[i] + 1
            for j in range(n-1,i,-1):
                a[j] = a[i]
            if(sco(a) > score):
                score = sco(a)
            break
    if (flag == False):
        break

print(str(score))

Submission status: Wrong Answer

Solution code:
# 解説を参考に作成


def solve():
    N, M, Q = map(int, input().split())
    abcd = [[int(i) for i in input().split()] for _ in range(Q)]

    def dfs(AA=[0], now_max=0):
        A = AA.copy()
        if len(A) == N + 1:
            new_max = 0
            for a, b, c, d in abcd:
                if A[b] - A[a] == c:
                    new_max += d
            now_max = max(now_max, new_max)
        else:
            for i in range(A[-1], M + 1):
                now_max = max(now_max, dfs(A + [i], now_max))
        return now_max

    print(dfs())


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
abcd_list = [list(map(int, input().split())) for _ in range(Q)]
Alist = []
def dfs(array):
    if len(array) == N:
        Alist.append(array)
    else:
        if not array:
            for i in range(M+1):
                dfs(array[:] + [i])
        else:
            for i in range(array[-1], M+1):
                dfs(array[:] + [i])
dfs([])
ans = 0
for A in Alist:
    res = 0
    for a, b, c, d in abcd_list:
        if A[b-1] - A[a-1] == c:
            res += d
    ans = max(ans, res)
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n, m, q = map(int, input().split())
    abcd = [list(map(int, input().split())) for _ in range(q)]

    arr = []

    def dfs(num, ai):
        if len(ai) == n:
            arr.append(ai)
        elif len(ai) < n:
            for i in range(num, 11):
                dfs(i, ai + [i])

    ans = 0

    dfs(1, [])

    for ai in arr:
        score = 0
        for a, b, c, d in abcd:
            if ai[b - 1] - ai[a - 1] == c:
                score += d
        if ans < score:
            ans = score

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Wrong Answer

Solution code:
n, m, q = list(map(int, input().split()))
a, b, c, d = zip(*[list(map(int, input().split())) for i in range(q)])

A = [1] * n
A[n-1] = 0
Ap = 0
while True:
    p0 = 0
    A[n-1] += 1
    #time.sleep(0.02)
    if A[0] == 9:
        break
    for i in range(n):
        if A[i] == 10:
            A[i-1] += 1
            A[i:] = [A[i-1]]*(n-i)


    #print(A)
    for i in range(q):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            p0 += d[i]
    Ap = max(Ap, p0)

print(Ap)

Submission status: Wrong Answer

Solution code:
n, m, q = list(map(int, input().split()))
a, b, c, d = zip(*[list(map(int, input().split())) for i in range(q)])

A = [1] * n
A[n-1] = 0
Ap = 0
while True:
    p0 = 0
    A[n-1] += 1
    #time.sleep(0.02)
    if A[0] == 9:
        break
    for i in range(n):
        if A[i] == 10:
            A[i-1] += 1
            A[i:] = [A[i-1]]*(n-i)


    #print(A)
    for i in range(q):
        if A[n-1] < 10 and A[b[i]-1] - A[a[i]-1] == c[i]:
            p0 += d[i]
    Ap = max(Ap, p0)

print(Ap)

Submission status: Wrong Answer

Solution code:
n, m, q = list(map(int, input().split()))
a, b, c, d = zip(*[list(map(int, input().split())) for i in range(q)])

A = [1] * n
A[n-1] = 0
Ap = 0
while True:
    p0 = 0
    A[n-1] += 1
    #time.sleep(0.02)
    if A[0] == 9:
        break
    for i in range(n):
        if A[i] == 9:
            A[i-1] += 1
            A[i:] = [A[i-1]]*(n-i)


    #print(A)
    for i in range(q):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            p0 += d[i]
    Ap = max(Ap, p0)

print(Ap)

Submission status: Wrong Answer

Solution code:
n, m, q = list(map(int, input().split()))
a, b, c, d = zip(*[list(map(int, input().split())) for i in range(q)])

A = [1] * n
A[n-1] = 0
Ap = 0
while True:
    p0 = 0
    A[n-1] += 1
    #time.sleep(0.02)
    for i in range(n-1, -1, -1):
        if A[i] >= 10:
            A[i-1] += 1
            A[i] = A[i-1]
    #print(A)
    if A[0] >= 10:
        break
    for i in range(q):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            p0 += d[i]
    Ap = max(Ap, p0)

print(Ap)

Submission status: Wrong Answer

Solution code:
from collections import deque


def calc(nums):
    ret = 0
    for a, b, c, d in req:
        if nums[b - 1] - nums[a - 1] == c:
            ret += d

    return ret


n, m, q = list(map(int, input().split()))
req = [list(map(int, input().split())) for _ in range(q)]

ans = 0

que = deque()

# [1]～[m]までキューに追加します。実は[1]だけでもいいです。考えてみてください。
for i in range(m + 1):
    que.append([i])

while que:
    seq = que.pop()

    if len(seq) == n:
        score = calc(seq)
        ans = max(ans, score)
    else:
        for i in range(seq[-1], m + 1):
            seq_next = seq + [i]
            que.append(seq_next)

print(ans)