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: Accepted

Solution code:
import itertools
n,m,q=map(int,input().split())
a=[]
for _ in range(q):
  b=list(map(int,input().split()))
  a.append(b)
  
g=list(range(1,m+1))
c=[]
for v in itertools.combinations_with_replacement(g,n):
  c.append(v)
  
ans1=[]
ans=0
for x in range(len(c)):
  d=c[x]
  ans1=0
  for r in range(q):
    a1=a[r][0]-1
    b1=a[r][1]-1
    c1=a[r][2]
    d1=a[r][3]
    if d[b1]-d[a1]==c1:
      ans1+=d1
      
  ans=max(ans,ans1)
  
print(ans)

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(q)]
ans=0
for i1 in range(1,m+1):
  for i2 in range(i1,m+1):
    for i3 in range(i2,m+1):
      for i4 in range(i3,m+1):
        for i5 in range(i4,m+1):
          for i6 in range(i5,m+1):
            for i7 in range(i6,m+1):
              for i8 in range(i7,m+1):
                for i9 in range(i8,m+1):
                  for i10 in range(i9,m+1):
                    tmp=0
                    arrs=[0,i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]
                    for a,b,c,d in arr:
                      if arrs[b]-arrs[a]==c:
                        tmp+=d
                    ans=max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations as combi

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

#/##//####
# M-1+N C N
max_num = 0
for l in combi(range(M-1+N), N):
    x = [t-s for t, s in zip(l, range(N))]
    # print(x)
    score = sum(d for a, b, c, d in ABCD if x[b-1]-x[a-1] == c)
    max_num = max(max_num, score)

print(max_num)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**6)

def score(Ans):
    t = 0
    for ai,bi,ci,di in zip(A,B,C,D):
        if Ans[bi]-Ans[ai]==ci:
            t += di
    return t

def dfs(Ans):
    if len(Ans)==n:
        return score(Ans)
    ans = 0
    prev_last = Ans[-1] if len(Ans)>0 else 0
    for v in range(prev_last, m):
        Ans.append(v)
        ans = max(ans, dfs(Ans))
        Ans.pop()
    return ans

n, m, q = map(int, readline().split())
A,B,C,D = [0]*q, [0]*q, [0]*q, [0]*q
for i in range(q):
    a,b,C[i],D[i] = map(int, readline().split())
    A[i] = a-1
    B[i] = b-1

print(dfs([]))

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
n,m,q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(q)]

ans = 0
for i in combinations_with_replacement(range(1,m+1), n):
  t = 0
  for j in abcd:
    if i[j[1]-1] - i[j[0]-1] == j[2]: t += j[3]
  ans = max(ans, t)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

A,B,C,D=[],[],[],[]

for i in range(Q):
    a,b,c,d=list(map(int,input().split()))
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)

Z=combinations_with_replacement(range(1,M+1),N)

M=0
for K in Z:
    X=0
    L=["*"]+list(K)
    for i in range(Q):
        if L[B[i]]-L[A[i]]==C[i]:
            X+=D[i]
    M=max(M,X)
print(M)

Submission status: Accepted

Solution code:
from collections import deque
N, M, Q = map(int, input().split())
I = [list(map(int, input().split())) for _ in range(Q)]

que = deque()
ans = 0
for i in range(1, M+1):
    que.append([i])

while que:
    seq = que.popleft()
    
    if len(seq) == N:
        p = 0
        for i in range(Q):
            if seq[I[i][1]-1] - seq[I[i][0]-1] == I[i][2]:
                p += I[i][3]
        ans = max(ans, p)
    else:
        for i in range(seq[-1], M+1):
            seq_next = seq + [i]
            que.append(seq_next)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n, m, q = map(int, input().split())
abcd = [0] * q
for i in range(q):
    abcd[i] = list(map(int, input().split()))

def dfs(seq):
    if len(seq) == n:
        yield seq
    else:
        if seq:
            last = seq[-1]
        else:
            last = 1
        for i in range(last, m+1):
            new_seq = seq.copy()
            new_seq.append(i)
            yield from dfs(new_seq)

seq = dfs([])
ans = 0
for s in seq:
    tmp_ans = 0
    for a, b, c, d in abcd:
        if s[b-1] - s[a-1] == c:
            tmp_ans += d
    ans = max(ans, tmp_ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools


def resolve(in_):
    n, m, q = map(int, next(in_).split())
    abcd = tuple(tuple(map(int, row.split())) for row in in_)
    # print(abcd)

    ans = 0
    for seq_a in itertools.combinations_with_replacement(range(1, m + 1), n):
        # print(seq_a)
        point = 0
        for a, b, c, d in abcd:
            if seq_a[b - 1] - seq_a[a - 1] == c:
                point += d
        ans = max(ans, point)

    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import itertools

n, m, q = [int(x) for x in stdin.readline().rstrip().split()]

A = []
for i in range(q):
    A.append([int(x) for x in stdin.readline().rstrip().split()])

nums = [x for x in range(1,m+1)]

max_point = 0
for balls in itertools.combinations_with_replacement(nums, n):
    point = 0
    for i in range(q):
        if balls[A[i][1]-1] - balls[A[i][0]-1] == A[i][2]: point = point + A[i][3]
    max_point = max([max_point, point])

print(max_point)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict,deque
from itertools import permutations
ml=lambda:map(int,input().split())
ll=lambda:list(map(int,input().split()))
ii=lambda:int(input())
ip=lambda:list(input())
ips=lambda:input().split()
sys.setrecursionlimit(10**6)
"""========main code==============="""


def check(lol,x):
    if(len(lol)==n):
        tp=0
        for j in v:
            a=j[0]
            b=j[1]
            c=j[2]
            d=j[3]
            if(lol[b-1]-lol[a-1]==c):
                tp+=d
            
        return tp
    k=0         
    for i in range(x,m+1):
        yo=lol[:]
        yo.append(i);
        k=max(k,check(yo,i))
    return k
    


n,m,q=ml()
lol=[]
for i in range(1,m+1):
    lol.append(i)


v=[]

for i in range(q):
   tmp=ll()
   v.append(tmp)



lol=[1]
print(check(lol,1))

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

n, m, q = map(int, input().split())
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())

ans = 0
for v in combinations_with_replacement(list(range(1, m + 1)), n):
    sm = 0
    for i in range(q):
        if v[b[i] - 1] - v[a[i] - 1] == c[i]:
            sm += d[i]
    ans = max(ans, sm)
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7
res = 0


def resolve():
    def dfs(v, A):
        global res
        if len(A) == n:
            total = 0
            for a, b, c, d in query:
                if A[b - 1] - A[a - 1] == c:
                    total += d
            res = max(res, total)
        else:
            for i in range(v, m + 1):
                A.append(i)
                dfs(i, A)
                A.pop()

    n, m, q = map(int, input().split())
    query = [list(map(int, input().split())) for _ in range(q)]
    dfs(1, [])
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import itertools

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

# (1,2,...,M)からN個選ぶ重複組み合わせを生成
# ex. N=3, M=4
# [(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 2, 2), (1, 2, 3), (1, 2, 4), (1, 3, 3), (1, 3, 4), (1, 4, 4),
# (2, 2, 2), (2, 2, 3), (2, 2, 4), (2, 3, 3), (2, 3, 4), (2, 4, 4), (3, 3, 3), (3, 3, 4), (3, 4, 4), (4, 4, 4)]

# (1,2,...,M)のリスト
l = range(1, M + 1)
nCr = list(itertools.combinations_with_replacement(l, N))
# print(nCr)

# 最終的な答え
ans = 0
for A in nCr:
    # 各組み合わせで得られる点数
    tmp = 0
    for a, b, c, d in abcd:
        if A[b - 1] - A[a - 1] == c:
            tmp += d
    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
def INT():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(map(int, input().split()))

def l_s(L):
    return "".join(map(str, L))

from itertools import combinations_with_replacement as cwr

N, M, Q = MI()
comb = [LI() for _ in range(Q)]
sequence = list(range(1, M + 1))
ans = 0

for A in cwr(sequence, N):
    tmp = 0
    A = list(A)
    for abcd in comb:
        a, b, c, d = abcd[0], abcd[1], abcd[2], abcd[3]
        if A[b - 1] - A[a - 1] == c:
            tmp += d
            
    ans = max(ans, tmp)
    
print(ans)

Submission status: Accepted

Solution code:
n,m,q = [int(_) for _ in input().split()]
a = []
b = []
c = []
d = []

for q in range(q):
  tmplist = [int(_) for _ in input().split()]
  a.append(tmplist[0])
  b.append(tmplist[1])
  c.append(tmplist[2])
  d.append(tmplist[3])

# Aという数列を再帰関数で求める
# {} → {A1, A2, A3...AN} の数

result=[]
def score(A):
  max_score = 0
  for i in range(q+1):
    if A[b[i]-1] - A[a[i]-1] != c[i]: # なぜマイナス１をしているのか？：ｑ
      continue
    else:
      max_score+= d[i]
  return max_score

def dfs(A):
  if len(A) == n+1: # 配列の個数はN個
    return score(A)
  result = 0
  past_data = A[-1]
  for v in range(past_data,m+1):
    A.append(v)
    result = max(result,dfs(A))
    A.pop()
  return result

print(dfs([1]))

Submission status: Accepted

Solution code:
import itertools

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

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

for A in nCr:
    tmp = 0
    for a, b, c, d in abcd:
        if A[b - 1] - A[a - 1] == c:
            tmp += d
    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
n, m, q = map(int, input().split())
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())

score = []

# 数列Aの全探索

import copy
def dfs(A):
    if len(A) == n+1:
        # score計算
        tmp = 0
        #print(A)
        for i in range(q):
            if A[b[i]] - A[a[i]] == c[i]:
                 tmp += d[i]
        score.append(tmp)
        return
    else:
        tmp = A[-1]
        arr = copy.copy(A)
        arr.append(tmp)
        while(arr[-1] <= m):
            dfs(arr)
            arr[-1] += 1  
dfs([1])

print(max(score))

Submission status: Accepted

Solution code:
import itertools

N, M, Q = map(int, input().split())
l = [i for i in range(1, M+1)]
qus = []
As = []
for _ in range(Q):
    b = list(map(int, input().split()))
    qus.append(b)
for v in itertools.combinations_with_replacement(l, N):
    a = list(v)
    A = 0
    for q in qus:
        pre = a[q[1]-1] - a[q[0]-1]
        if pre == q[2]:
            A += q[3]
    As.append(A)
print(max(As))

Submission status: Accepted

Solution code:
import itertools
N, M, Q = map(int, input().split())
a = []
b = []
c = []
d = []
for q in range(Q):
    aq, bq, cq, dq = map(int, input().split())
    a.append(aq)
    b.append(bq)
    c.append(cq)
    d.append(dq)

max_answer = 0
for A in itertools.combinations_with_replacement(range(1, M + 1), N):
    # print(A)
    answer = 0
    for i in range(Q):
        # print(a[i], b[i], c[i], d[i])
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            answer += d[i]
    # print(answer)
    if max_answer < answer:
        max_answer = answer
print(max_answer)

Submission status: Accepted

Solution code:

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


def dfs(x):
    if len(x) == N + 1:
        res = 0
        for a, b, c, d in X:
            if x[b] - x[a] == c:
                res += d
        return res

    res = 0
    for i in range(max(1, x[-1]), M + 1):
        x.append(i)
        res = max(res, dfs(x))
        x.pop()

    return res


print(dfs([0]))

Submission status: Accepted

Solution code:
import itertools
n,m,q = list(map(int, input().split()))
abcd = [[0] * 4 for _ in range(q)]
for i in range(q):
  abcd[i] = list(map(int, input().split()))

M = itertools.combinations_with_replacement(range(m),n)
ans = 0
for A in M:
  for i in range(1,n):
    if A[i] <= A[i-1]:break
  temp = 0
  for i in range(q):
    a = A[abcd[i][0]-1]
    b = A[abcd[i][1]-1]
    c = abcd[i][2]
    d = abcd[i][3]
    if b - a == c:
      temp += d
  ans = max(ans,temp)

print(ans)

Submission status: Accepted

Solution code:
n,m,q = map(int,input().split())
A = [0]*q
B = [0]*q
C = [0]*q
D = [0]*q



for i in range(q):
    a,b,c,d = map(int,input().split())
    A[i] = a
    B[i] = b
    C[i] = c
    D[i] = d

walist = []
for i in range(2**(n+m-1)):
    if bin(i).count("1") == n:
        wa = 0
        seq = []
        value = 1
        for j in range(n+m-1):
            if (i>>j)&1 == 1:
                seq += [value]
            else:
                value += 1
        for k in range(q):
            if seq[B[k]-1] - seq[A[k]-1] == C[k]:
                wa += D[k]
        walist += [wa]

print(max(walist))

Submission status: Accepted

Solution code:
import itertools
n,m,q = map(int, input().split())
p=[[0,0,0,0]]
for i in range(q):
    p.append(list(map(int, input().split())))

ans=0

for tmp in itertools.combinations_with_replacement(range(1,m+1),n):
    tokuten=0
    for gyou in range(1,q+1):
        if tmp[p[gyou][1]-1]-tmp[p[gyou][0]-1]==p[gyou][2]:
            tokuten+=p[gyou][3]
    ans=max(ans,tokuten)

print(ans)

Submission status: Accepted

Solution code:
N,M,Q = map(int, input().split())
ab = tuple(tuple(map(int, input().split())) for _ in range(Q))
ans = 0
def dfs(A):
    global ans
    if len(A) == N:
        tmp = 0
        for i in range(Q):
            a,b,c,d = ab[i]
            if (A[b-1]-A[a-1]) == c:
                tmp += d
        if tmp > ans:
            ans = tmp


    else:
        last = A[-1] if len(A) > 0 else 1
        for i in range(last, M+1):
            A.append(i)
            dfs(A)
            A.pop()
dfs([])
print(ans)

Submission status: Accepted

Solution code:
import itertools 
N,M,Q = map(int,input().split())
ans = 0
search_list = list(range(M))
value_list = [[0]*4 for _ in range(Q)]
for i in range(Q):
    value_list[i]=list(map(int,input().split()))
for i in itertools.combinations_with_replacement(search_list,N):
    value = 0
    for test in value_list:
        if(i[test[1]-1]-i[test[0]-1]==test[2]):
            value+=test[3]
    ans = max(ans,value)
print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M,Q = map(int,input().split())
cc = [list(map(int,input().split())) for i in range(Q)]
a = [i for i in range(1,M+1)]
max_count = -float('inf')
for i in itertools.combinations_with_replacement(a,N):
  count = 0
  for j in cc:
    if i[j[1]-1] - i[j[0]-1] == j[2]:
      count += j[3]
  max_count = max(max_count,count)
print(max_count)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,m,q = inpm()
ans = 0
abcd = []
for _ in range(q):
    a,b,c,d = inpm()
    abcd.append((a,b,c,d))

for e in itertools.combinations_with_replacement(range(m),n):
    cnt = 0
    for i in range(q):
        [a,b,c,d] = abcd[i]
        if e[b-1] - e[a-1] == c:
            cnt += d
    ans = max(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
def permutations(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutations(data):
                ret.append([i] + j)

        return ret
        

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

bou = [1] * N
ball = [2] * (M-1)

junretsu = permutations(bou + ball)

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

ans = 0
for i in range(len(junretsu)):
    souwa = 0
    check = 0
    A = []
    for j in range(N+M-1):
        if junretsu[i][j] == 1:
            A.append(j - check + 1)
            check += 1
    for j in range(Q):
        if (A[b[j]-1] - A[a[j]-1]) == c[j]:
            souwa += d[j]
    
    ans = max(ans, souwa)

print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M,Q = map(int,input().split())
list_a = []
for i in range(Q):
  a = list(map(int,input().split()))
  list_a.append(a)
list_num =[]
max_num = 0
for i in range(1,M+1):
  list_num.append(i)
num = list(itertools.combinations_with_replacement(list_num, N))
for i in num:
  count=0
  for j in list_a:
    if i[j[1]-1]-i[j[0]-1]==j[2]:
      count+=j[3]
  max_num = max(count,max_num)
print(max_num)

Submission status: Accepted

Solution code:
n, m, q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(q)]
ans = 0
seq = [0] * 10

def dfs(depth, tail):
    global ans, seq
    if depth == n:
        s = 0
        for a, b, c, d in abcd:
            a -= 1
            b -= 1
            if seq[b] - seq[a] == c:
                s += d
        ans = max(ans, s)
        return

    for i in range(tail, m + 1):
        seq[depth] = i
        dfs(depth + 1, i)

dfs(0, 1)
print(ans)

Submission status: Accepted

Solution code:
n,m,q = map(int,input().split())
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())
    a[i] -= 1 # インデックス補正
    b[i] -= 1 
    
def score(A):
    x = 0
    for ai,bi,ci,di in zip(a,b,c,d):
        if A[bi] - A[ai] == ci:
            x += di
    return x

def dfs(A):
    # 終端条件 --- 3 重ループまで回したら処理して打ち切り
    if len(A) == n:
        #print(A)
        return score(A)
    res = 0
    # 単調増加するように制限
    pre = A[-1] if len(A) > 0 else 0 
    for v in range(pre, m):
        A.append(v) # 次のノードへの遷移
        res = max(res,dfs(A))      # 再帰呼出し
        A.pop()     # 一回元に戻す (これが結構ポイント appendする前の状態に戻している)
    return res

print(dfs([]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

def dfs(lst):
    if len(lst) == n:
        return calc(lst)
    
    x = lst[-1]
    ret = 0
    for i in range(x, m+1):
        ret = max(ret, dfs(lst + [i]))
    return ret

n, m, q = LI()
abcd = [LI() for _ in range(q)]
ans = dfs([1])
print(ans)

Submission status: Accepted

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

def conb(l,m):#   自作itertools.combinations_with_replacement(l, n)
    ls = l.copy()
    if ls[len(ls)-1] < m:
            ls[len(ls)-1] += 1
            return ls
    for i in range(len(ls)-2,-1,-1):
        if ls[i] < m:
            ls[i] += 1
            for j in range(len(ls)-1,i,-1):
                ls[j] = ls[i]
            return ls
    return None
ls = [[1]*n]
i = 0
while(1):
    x = conb(ls[i],m)
    if x != None:
        ls.append(x)
    else:
        break
    i += 1
abcd = []
l = [i for i in range(1,m+1)]

ans = 0

for j in range(q):
    abcd.append(list(map(int,input().split())))
for v in ls:
    #print(v)
    sum = 0
    for j in range(q):
        if v[abcd[j][1]-1] - v[abcd[j][0]-1] == abcd[j][2]:
            sum += abcd[j][3]
    ans = max(ans,sum)
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

ls = itertools.combinations_with_replacement([i + 1 for i in range(m)], n)

ans = 0
for A in ls:
    total = 0
    for a, b, c, d in abcd:
        if A[b - 1] - A[a - 1] == c:
            total += d
    ans = max(ans, total)
print(ans)

Submission status: Accepted

Solution code:
import itertools

n,m,q = map(int,input().split())
abcd = []
l = [i for i in range(1,m+1)]
h = itertools.combinations_with_replacement(l, n)
ans = 0

for i in range(q):
    abcd.append(list(map(int,input().split())))
for v in h:
    sum = 0
    for i in range(q):
        if v[abcd[i][1]-1] - v[abcd[i][0]-1] == abcd[i][2]:
            sum += abcd[i][3]
    ans = max(ans,sum)
print(ans)

Submission status: Accepted

Solution code:
# C Many Requirements

from itertools import combinations_with_replacement as com

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

C = []
for q in range(Q):
  C.append(tuple(map(int, input().split())))

As = com([i for i in range(1, M+1)], N)

ans = 0
for A in As:
  point = 0
  for Ci in C:
    if A[Ci[1]-1] - A[Ci[0]-1] == Ci[2]:
      point += Ci[3]
  ans = max(ans, point)

print(ans)

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
abcd=[list(map(int,input().split())) for i in range(q)]

from itertools import combinations_with_replacement as comb_rplc
cmb = comb_rplc(range(1,m+1),n)
result = 0
for A in cmb:
  tmp = 0
  for a,b,c,d in abcd:
    if A[b-1] - A[a-1] == c:
      tmp += d
  result = max(tmp, result)
print(result)

Submission status: Accepted

Solution code:
import itertools
n,m,q=map(int,input().split())
abcd=[tuple(map(int,input().split())) for _ in range(q)]
h=[]
for i in range(1,m+1):
    h.append(i)
ans=0
for j in itertools.combinations_with_replacement(h,n):
    temp=0
    for a,b,c,d in abcd:
        if j[b-1]-j[a-1]==c:
            temp+=d 
    ans=max(ans,temp)
print(ans)

Submission status: Accepted

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

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

A = itertools.combinations_with_replacement(range(1,M+1),N)

for Ai in A:
    point = 0
    for a,b,c,d in abcd:
        if Ai[b-1] - Ai[a-1] == c:
            point += d
    ans= max(ans,point)
print(ans)

Submission status: Accepted

Solution code:
import itertools
N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for i in range(Q)]
total = []
for A in itertools.combinations_with_replacement(range(1, M+1), N):
  score = 0
  for a,b,c,d in abcd:
    if A[b-1]-A[a-1] == c:
      score += d
    total.append(score)
print(max(total))

Submission status: Accepted

Solution code:
import itertools
N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for i in range(Q)]
ans = 0
for A in itertools.combinations_with_replacement(range(1, M+1), N):
  score = 0
  for i in range(Q):
    a = abcd[i][0]
    b = abcd[i][1]
    c = abcd[i][2]
    d = abcd[i][3]
    if A[b-1]-A[a-1] == c:
      score += d
  ans = max(ans,score)
print(ans)

Submission status: Accepted

Solution code:
import itertools
N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for i in range(Q)]
ans = 0
for A in itertools.combinations_with_replacement(range(1, M+1), N):
  score = []
  for i in range(Q):
    a = abcd[i][0]
    b = abcd[i][1]
    c = abcd[i][2]
    d = abcd[i][3]
    if A[b-1]-A[a-1] == c:
      score.append(d)
  ans = max(ans,sum(score))
print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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


ans = 0
for A in itertools.combinations_with_replacement(range(1, M+1), N):
  score = []
  for i in range(Q):
    a = abcd[i][0]
    b = abcd[i][1]
    c = abcd[i][2]
    d = abcd[i][3]
    if A[b-1]-A[a-1] == c:
      score.append(d)
  ans = max(ans,sum(score))
print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

score = []
ans = 0
for A in itertools.combinations_with_replacement(range(1, M+1), N):
  for i in range(Q):
    a = abcd[i][0]
    b = abcd[i][1]
    c = abcd[i][2]
    d = abcd[i][3]
    if A[b-1]-A[a-1] == c:
      score.append(d)
  if ans <= sum(score):
    ans = sum(score)
  score.clear()
print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

d_list = []
sum_d = 0
for A in itertools.combinations_with_replacement(range(1, M+1), N):
  for i in range(Q):
    a = abcd[i][0]
    b = abcd[i][1]
    c = abcd[i][2]
    d = abcd[i][3]
    if A[b-1]-A[a-1] == c:
      d_list.append(d)
  if sum_d <= sum(d_list):
    sum_d = sum(d_list)
  d_list.clear()
print(sum_d)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

d_list = []
sum_d = 0
for A in itertools.combinations_with_replacement(range(1, M+1), N):
  for i in range(Q):
    a = abcd[i][0]
    b = abcd[i][1]
    c = abcd[i][2]
    d = abcd[i][3]
    if A[b-1]-A[a-1] == c:
      d_list.append(abcd[i][3])
  if sum_d <= sum(d_list):
    sum_d = sum(d_list)
  d_list.clear()
print(sum_d)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
d_list = []
sum_d = 0
N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for i in range(Q)]
ans = 0
A = [1 for i in range(N)]
for A in itertools.combinations_with_replacement(range(1, M+1), N):
  for i in range(Q):
    a = abcd[i][0]
    b = abcd[i][1]
    c = abcd[i][2]
    d = abcd[i][3]
    if A[b-1]-A[a-1] == c:
      d_list.append(abcd[i][3])
  if sum_d <= sum(d_list):
    sum_d = sum(d_list)
  d_list.clear()
print(sum_d)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
d_list = []
sum_d = 0
N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for i in range(Q)]
ans = 0
A = [1 for i in range(N)]
for A in itertools.combinations_with_replacement(range(1, M+1), N):
  for i in range(Q):
    if A[abcd[i][1]-1]-A[abcd[i][0]-1] == abcd[i][2]:
      d_list.append(abcd[i][3])
  if sum_d <= sum(d_list):
    sum_d = sum(d_list)
  d_list.clear()
print(sum_d)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

class Combination_with_repetition():
    def getPattern(self, arr :list, r :int) -> list:
        self._selected=[]
        self._all_pattern=[]
        
        self._make(arr,r)
        return self._all_pattern
        
    def _make(self, arr :list, r :int):
        if r == 0:
            self._all_pattern.append(self._selected[:])
            return 
        
        for i in range(len(arr)):
            self._selected.append( arr[i] )
            self._make(arr[i:],r-1)
            
            self._selected.pop()  # Backtracking

#-----
N,M,Q = list(map(int, input().rstrip().split()))
abcd_list = [list(map(int, input().rstrip().split())) for i in range(Q)]

#-----
comb_rep = Combination_with_repetition()
pattern = comb_rep.getPattern( list(range(1, M+1)) , N)


max_sum = 0

for pat in pattern:
    tmp_sum = 0
    
    for a,b,c,d in abcd_list:
        if ( pat[b-1] - pat[a-1] ) == c:
            tmp_sum += d
    
    max_sum = max(max_sum, tmp_sum)

print(max_sum)

Submission status: Accepted

Solution code:
from copy import deepcopy
n, m, q = map(int, input().split())
tuples = [tuple(map(int, input().split())) for i in range(q)]
As = [[1]*n]
def next(A, i):
    if i == 0 and A[i] == m:
        return
    if A[i] == m:
        next(A, i-1)
    elif A[i] < m:
        if (i < n - 1 and A[i] < A[i+1]) or (i == n-1):
            A1 = deepcopy(A)
            A1[i] += 1
            As.append(A1)
            next(A1, i)
        if i > 0 and A[i] > A[i-1]:
            A2 = deepcopy(A)
            next(A2, i-1)
    elif i == 0:
        A1 = deepcopy(A)
        next(A1, n-1)
next([1]*(n), n-1)
def check(A):
    score = 0
    for a, b, c, d in tuples:
        if A[b-1] - A[a-1] == c:
            score += d
    return score
ans = 0
for A in As:
    score = check(A)
    ans = max(ans, score)
print (ans)

Submission status: Accepted

Solution code:
# 視点を変えてやる全探索 実は条件よりAを全列挙することが可能

# rec, 1からじゃなくて0からにしてたせいか1ケースでWA????

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


def rec(arr):
    if len(arr) == n:
        koho.append(arr)
    else:
        for i in range(arr[-1], m + 1):
            nex_arr = arr[:]
            nex_arr.append(i)
            rec(nex_arr)


# これ 0からにしてたんだけど べつに影響なくないか？？？？？？
for i in range(1, m + 1):
    rec([i])
ans = 0

qs = []
for _ in range(q):
    qs.append(list(map(int, input().split())))

for arr in koho:
    tmp = 0
    for abcd in qs:
        if arr[abcd[1] - 1] - arr[abcd[0] - 1] == abcd[2]:
            tmp += abcd[3]
    ans = max(ans, tmp)
print(ans)