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:
N,M,Query = map(int,input().split())
from itertools import combinations_with_replacement
P = tuple(combinations_with_replacement(range(1,M+1),N))
Q = []
for _ in range(Query):
    a,b,c,d = map(int,input().split())
    Q.append((a,b,c,d))
    answer = 0
for p in P:
    ans = 0
    for a,b,c,d in Q:
        if p[b-1]-p[a-1]==c:
            ans += d
    answer = max(ans,answer)
print(answer)

Submission status: Accepted

Solution code:
import itertools
N, M, Q = [int(x) for x in input().split(" ")]

conditions = [[int(x) for x in input().split(" ")] for _ in range(Q)]

def add(l, N):
    if len(l) == 0:
        b = 1
    else:
        b = l[-1]
    ans = []
    for i in range(b, N+1):
        ans.append(l + [i])
    return ans

L = [[]]
for _ in range(N):
    nex = []
    for l in L:
        nex.extend(add(l, M))
    L = nex

smax = 0
for l in L:
    s = 0
    for c in conditions:
        if l[c[1]-1] - l[c[0]-1] == c[2]:
            s += c[3]
    if s > smax:
        smax = s
print(smax)

Submission status: Accepted

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

def score(l):
    res = 0
    for i in range(q):
        temp = l[b[i] - 1] - l[a[i] - 1]
        if temp == c[i]:res += d[i]

    return res

def dfs(l):
    global ans
    if len(l) == n:
        ans = max(ans, score(l))
        return #中で使われている関数の終了

    if l:
        temp = l[-1]
    else:
        temp = 1
    for v in range(temp, m + 1):
        l.append(v)
        dfs(l)
        l.pop()

ans = 0
dfs([])
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations_with_replacement

input = sys.stdin.readline


def main():
    N, M, Q = map(int, input().split())
    abcd = [None] * Q
    for i in range(Q):
        abcd[i] = list(map(int, input().split()))
        abcd[i][0] -= 1
        abcd[i][1] -= 1

    ans = 0
    for A in combinations_with_replacement(range(1, M + 1), N):
        score = 0
        for a, b, c, d in abcd:
            if A[b] - A[a] == c:
                score += d
        if score > ans:
            ans = score

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


# 昇順列の巡回
def ascending(N, M):
    # 長さN, 値0からM-1まで
    A = [0] * N
    yield A
    while True:
        # Mより小さい最後の桁
        k = None
        for i in reversed(range(N)):
            if A[i] < M - 1:
                k = i
                break
        if k is not None:
            A[k] += 1
            for j in range(k + 1, N):
                A[j] = A[k]
        else:
            return
        yield A


INF = float("inf")
MOD = 10**9 + 7


def main():
    n, m, q = MAP()
    abcd = ZIP(q)

    def point(A):
        tot = 0
        for a, b, c, d in abcd:
            if A[b - 1] - A[a - 1] == c:
                tot += d
        return tot

    # 昇順列を巡回する
    ans = 0
    for a in ascending(n, m):         # O(N)
        p = point(a)
        # print(a)
        if ans <= p:
            ans = p
    print(ans)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7


def main():
    n, m, q = MAP()
    abcd = ZIP(q)

    def ascending(X):
        for i in range(1, n):
            if A[i - 1] > A[i]:
                return False
        return True

    def point(A):
        tot = 0
        for a, b, c, d in abcd:
            if A[b - 1] - A[a - 1] == c:
                tot += d
        return tot

    def forward(A):
        # Mより小さい最後の桁
        k = None
        for i in reversed(range(n)):
            if A[i] < m:
                k = i
                break
        if k is not None:
            A[k] += 1
            for j in range(k + 1, n):
                A[j] = A[k]
        else:
            A[0] = INF

    # 昇順列を巡回する
    A = [1] * n
    ans = 0
    while ascending(A):         # O(N)
        # print(A)
        p = point(A)
        if ans <= p:
            ans = p
        forward(A)
    print(ans)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

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

num=1
seed = [[i] for i in range(1,m+1)]
while num!=n:
  num+=1
  tmp_list = []
  while seed:
    tmp = seed.pop()
    for i in range(tmp[-1],m+1):
      tmp_list.append(tmp+[i])
  seed = tmp_list.copy()

max_score = 0
visited = set()
for arr in seed:
  score = 0
  for arr_2 in list_:
    if arr[arr_2[1]-1] - arr[arr_2[0]-1] == arr_2[2]:
      score+=arr_2[3]
      max_score = max(max_score, score)
print(max_score)

Submission status: Accepted

Solution code:
#!usr/bin/env pypy3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate, combinations_with_replacement, compress
import sys
import math
import bisect
 
 
def LI(): return [int(x) for x in sys.stdin.readline().split()]
 
 
def I(): return int(sys.stdin.readline())
 
 
def LS(): return [list(x) for x in sys.stdin.readline().split()]
 
 
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
 
 
def IR(n):
    return [I() for i in range(n)]
 
 
def LIR(n):
    return [LI() for i in range(n)]
 
 
def SR(n):
    return [S() for i in range(n)]
 
 
def LSR(n):
    return [LS() for i in range(n)]
 
 
sys.setrecursionlimit(1000000)
 
 
def main():
    N, M, Q = LI()
    abcd = [LI() for _ in range(Q)]
    ans = 0
 
    for A in combinations_with_replacement(range(1, M + 1), N):
        tmp = 0
        for (a, b, c, d) in abcd:
            tmp += d if (A[b-1] - A[a-1] == c) else 0
        ans = max(ans, tmp)
    print(ans)
 
 
main()

Submission status: Accepted

Solution code:
#!usr/bin/env pypy3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate, combinations_with_replacement, compress
import sys
import math
import bisect


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def LS(): return [list(x) for x in sys.stdin.readline().split()]


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


def LIR(n):
    return [LI() for i in range(n)]


def SR(n):
    return [S() for i in range(n)]


def LSR(n):
    return [LS() for i in range(n)]


sys.setrecursionlimit(1000000)


def main():
    N, M, Q = LI()
    abcd = [LI() for _ in range(Q)]
    ans = 0

    for A in combinations_with_replacement(range(1, M + 1), N):
        tmp = 0
        for (a, b, c, d) in abcd:
            tmp += d if (A[b-1] - A[a-1] == c) else 0
        ans = max(ans, tmp)
    print(ans)


main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))


n,m,q = inpl()
abc = [inpl() for _ in range(q)]
q = deque()
q.append([1])
res = 0
while q:
    now = q.popleft()
    if len(now) == n+1:
        # print(now)
        ans = 0
        for i,x in enumerate(abc):
            a,b,c,d = x
            if now[b] - now[a] == c:
                ans += d
        res = max(ans, res)
        continue
    for i in range(now[-1], m+1):
        q.append(now + [i])
print(res)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as combi

N, M, Q = map(int, input().split())
a = [0] * Q
b = [0] * Q
c = [0] * Q
d = [0] * Q
l = [i+1 for i in range(M)]
point = 0

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

for v in combi(l, N):
    tmp = 0
    for j in range(Q):
        if v[b[j]-1] - v[a[j]-1] == c[j]:
            tmp += d[j]
    point = max(point, tmp)

print(point)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as C

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_ = list(range(1, M + 1))
A_ = list(C(A_, N))

ans = 0
ans_ = 0
for A in A_:
    ans_ = 0
    for i in range(Q):
        if A[b[i] - 1] - A[a[i] - 1] == c[i]:
            ans_ += d[i]
    if ans < ans_:
        ans = ans_

print(ans)

Submission status: Accepted

Solution code:
def dfs(A):
    if len(A) == n+1:
        p = 0
        for i in range(q):
            if A[b[i]]-A[a[i]] == c[i]:
                p += d[i]
        global ans
        if p > ans:
            ans = p
        return
    num = A[-1]
    global m
    while num <= m:
        dfs(A[:]+[num])
        num += 1
                    

if __name__ == "__main__":
    n, m, q = map(int, input().split())
    a, b, c, d = [None]*q, [None]*q, [None]*q, [None]*q
    for i in range(q):
        a[i], b[i], c[i], d[i] = map(int, input().split())
    ans = 0
    dfs([1])
    print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as comb_rplc

N, M, Q = list(map(int, input().split()))
A = []
B = []
C = []
D = []
for i in range(Q):
    in1, in2, in3, in4 = list(map(int,input().split()))
    A.append(in1 - 1)
    B.append(in2 - 1)
    C.append(in3)
    D.append(in4)
    
ans = 0
for seq in comb_rplc(range(1, M + 1), N):
    temp = 0
    for i in range(Q):
        if seq[B[i]] - seq[A[i]] == C[i]:
            temp += D[i]
        ans = max(ans, temp)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as comb_rplc
n,m,q = map(int, input().split())
arr = []

for i in range(q):
  arr.append(list(map(int, input().split())))
  
score_max = 0
for seq in comb_rplc(range(1, (m+1)), n):
  score = 0
  
  for a,b,c,d in arr:
    if seq[b-1]-seq[a-1] == c:
      score += d
      
  if score > score_max:
    score_max = score
    
print(score_max)

Submission status: Accepted

Solution code:
import itertools

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

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

print(maxv)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

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

l = []

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

ans = 0
stack = [[1]]

while stack:
    a = stack.pop()
    if len(a) == N:
        score = 0
        for j in l:
            if a[j[1]-1] - a[j[0]-1] == j[2]:
                score += j[3]   
        ans = max(score, ans)
    else:
        for k in range(a[-1], M+1):
            s = a[:]
            s.append(k)
            stack.append(s)
print(ans)

Submission status: Accepted

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

def calc(x):
    ans = 0
    for a, b, c, d in A:
        if int(x[b-1]) - int(x[a-1]) == c:
            ans += d
    return ans

q = deque([[1]])
ans = 0
while q:
    tmp = q.popleft()
    if len(tmp) == N:
        ans = max(ans, calc(tmp))
    else:
        for i in range(tmp[-1], M+1):
            q.append(tmp+[i])

print(ans)

Submission status: Accepted

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

def calc(x): # type(x) == str型
    ans = 0
    for a, b, c, d in A:
        if int(x[b-1]) - int(x[a-1]) == c:
            ans += d
    return ans

q = deque([[1]]) # 外の括弧はdeque()にイテラブル渡すため、内の括弧は数列を[1, 2, 3]というようにリストで管理するため
ans = 0
while q:
    tmp = q.popleft() #>>> [1]
    if len(tmp) == N:
        ans = max(ans, calc(tmp))
    else:
        for i in range(tmp[-1], M+1): # range(1, M+1)
            q.append(tmp+[i])

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

def dfs(a_l):
  if len(a_l)==n:
    global ans
    t_ans=0
    for a,b,c,d in l:
      a-=1
      b-=1
      if (a_l[b]-a_l[a]==c):
        t_ans+=d
    ans=max(ans,t_ans)

    return

  a_last=a_l[-1]
  for i in range(a_last,m+1):
    dfs(a_l+[i])

ans=0
for i in range(1,m+1):
  dfs([i])

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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

ans = 0
que = deque()
for i in range(1, m + 1):
  que.append([i])
  
while que:
  seq = que.popleft()
  
  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)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as comb_rplc

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

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

ans = 0

for seq in comb_rplc(range(1 , (m + 1)), n):
  score = 0
  
  for a, b, c, d in req:
    if seq[b - 1] - seq[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())
pairs = []
for i in range(q):
    pairs.append(list(map(int, input().split())))

elem = [i for i in range(1, m+1)]

# elemからn回くじを引いて，出た値を昇順にソートする．引いたくじはすぐにelemに戻す．この全組み合わせをリストで返す．
candidates = list(itertools.combinations_with_replacement(elem, n))

dsummax = 0
for cand in candidates:
    dsum = 0
    for i in range(q):
        if cand[pairs[i][1]-1]-cand[pairs[i][0]-1] == pairs[i][2]:
            dsum += pairs[i][3]
    if dsummax < dsum:
        dsummax = dsum

print(dsummax)

Submission status: Accepted

Solution code:
import itertools

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

a = [0] * q
b = [0] * q
c = [0] * q
d = [0] * q

for i in range(q):
  a1,b1,c1,d1 = map(int,input().split())
  a[i] = a1
  b[i] = b1
  c[i] = c1
  d[i] = d1

x = itertools.combinations_with_replacement(range(1,m+1),n)
tmp = 0
ans = 0
for xi in x:
  tmp = 0

  for i in range(q):
    if xi[b[i]-1] - xi[a[i]-1] == c[i]:
      tmp += d[i]
  ans = max(ans,tmp)

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

A=[]
for i in range(Q):
    A.append(list(map(int,input().split())))
    A[i][0] -= 1
    A[i][1] -= 1

score = 0
max = 0

for iter in itertools.combinations_with_replacement(range(1,M+1),N):

    score = 0
    for i in range(Q):
        if iter[A[i][1]] - iter[A[i][0]] == A[i][2]:
            score += A[i][3]

    if max < score:
        max = score


print(max)

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())
    
import itertools
A = list(itertools.combinations_with_replacement(range(1,M+1), N))
ans = 0
for j in A:
    temp = 0
    for i in range(Q):
        if j[b[i]-1]-j[a[i]-1] == c[i]:
            temp += d[i]
    ans = max(ans,temp)
print(ans)

Submission status: Accepted

Solution code:
import itertools

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


ans = 0
for iter in itertools.combinations_with_replacement(range(1, m+1), n):
    score = 0
    for i in range(q):
        a, b, c, d = L[i]
        if iter[b-1]-iter[a-1]==c:
            score += d

    ans = max(ans, score)

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

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

ans = 0
for i in combinations_with_replacement(range(1, M+1), N):
    tmp = 0
    for a, b, c, d in A:
        if i[b-1] - i[a-1] == c:
            tmp += d
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
n, m, q=map(int, input().split())
l=[]
for _ in range(q):
  l.append(list(map(int, input().split())))
#print(l)
import itertools as itl
gl=list(range(1, m+1))  # 1からmのリスト
#print(gl)          
ans=0
for v in itl.combinations_with_replacement(gl, n): #1からのなかから、n個抽出
  check=0
  for i in range(q):
    if v[l[i][1]-1]-v[l[i][0]-1]==l[i][2]:
      check+=l[i][3]
  ans=max(check, ans)
print(ans)

Submission status: Accepted

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

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

ans = 0
for a in range(1, M+1):
    for b in range(a, M+1):
        for c in range(b, M+1):
            for d in range(c, M+1):
                for e in range(d, M+1):
                    for f in range(e, M+1):
                        for g in range(f, M+1):
                            for h in range(g, M+1):
                                for i in range(h, M+1):
                                    for j in range(i, M+1):
                                        tmp = 0
                                        MM = [a, b, c, d, e, f, g, h, i, j][:N]
                                        for ai, bi, ci, di in A:
                                            if MM[bi-1]-MM[ai-1] == ci:
                                                tmp += di
                                        ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N, M, Q = getNM()
query = [getList() for i in range(Q)]

# 数列Aについて得点計算
def counter(array):
    cnt = 0
    for i in range(Q):
        A_b = array[query[i][1] - 1]
        A_a = array[query[i][0] - 1]
        c = query[i][2]
        point = query[i][3]

        if A_b - A_a == c:
            cnt += point
    return cnt

ans = 0
# 重複組み合わせを生成
def rep_comb_pow_2(i, array):
    global ans
    if i == N:
        opt = counter(array)
        ans = max(ans, opt)
        return

    # 1スタート
    last = 1
    if len(array) > 0:
        last = array[-1]

    for j in range(last, M + 1):
        new_array = array + [j]
        rep_comb_pow_2(i + 1, new_array)

# 実行
rep_comb_pow_2(0, [])

print(ans)

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 i in range(q)]
ans = 0
for i in combinations_with_replacement(range(1, m + 1), n):
    cnt = 0
    for a, b, c, d in abcd:
        if i[b - 1] - i[a - 1] == c:
            cnt += d
    ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
# 数列生成
from itertools import combinations
N, M, Q = map(int, input().split())
ls = []
for i in range(Q):
    ls.append([int(j) for j in input().split()])
V = [[] for i in range(N+1)]
for i in range(1, M+1):
    V[1].append([i])

for i in range(1, N):
    for v in V[i]:
        b = v[-1]
        for x in range(b, M+1):
            V[i+1].append(v + [x])
ans = 0
for x in V[-1]:
    cur = 0
    for z in ls:
        if x[z[1]-1] - x[z[0]-1] == z[2]:
            cur += z[3]
    ans = max(ans, cur)
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
        return
    else:
        if not seq:
            last = 1
        else:
            last = seq[-1]
    for i in range(last, m+1):
        new_seq = seq.copy()
        new_seq.append(i)
        yield from dfs(new_seq)

ans = 0
for s in dfs([]):
    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:
from itertools import combinations_with_replacement 

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

Qset = []

for i in range(Q):
    a = list(map(int, input().split()))
    Qset.append(a)

ans = 0
for num in combinations_with_replacement(range(1, M+1), N):
    ans_temp = 0
    for j in Qset:
        if j[2] == num[j[1]-1] - num[j[0]-1]:
            ans_temp += j[3]

    ans = max(ans, ans_temp)

print(ans)

Submission status: Accepted

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

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] = list(map(int, input().split()))

ans = 0
X = [i for i in range(1,M+1)]
for tup in combinations_with_replacement(X,N):
    total = 0
    for i in range(Q):
        if tup[B[i]-1] - tup[A[i]-1] == C[i]:
            total += D[i]
    ans = max(ans,total)

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as comb_rplc
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

def dfs(A):
	ans=0
	if len(A)==n:#数列が完成
		score1=0
		for i in range(q):
			if A[b[i]-1]-A[a[i]-1]==c[i]:
				score1+=d[i]
		return score1
	else:
		for i in range(A[-1],m+1):
			A_next=A+(i,)
			score=dfs(A_next)
			ans=max(ans,score)
	return ans
	
score=dfs((1,))
ans=max(ans,score)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as comb_rplc
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 A in comb_rplc(range(1,m+1),n):
	sum=0
	for i in range(q):
		if A[b[i]-1]-A[a[i]-1]==c[i]:
			sum=sum+d[i]
	if sum>=ans:
		ans=sum

print(ans)

Submission status: Accepted

Solution code:
N,M,Q=map(int,input().split())
from copy import copy
A=[]
def DFS(n,s):
    if len(s)==n:
        A.append(copy(s))
        return
    ss=s[-1]
    for i in range(ss,M+1):
        s.append(i)
        DFS(n,s)
        s.pop()

DFS(N,[1])

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

L=len(A)
ans=0
for i in range(L):

    point=0
    for j in range(Q):
        a,b,c,d=q[j]
        if A[i][b-1]-A[i][a-1]==c:
            point+=d
    ans=max(ans,point)
print(ans)

Submission status: Accepted

Solution code:
N,M,Q = map(int,input().split())
numcomb = [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):
                                        temp = 0
                                        arrs = [0,i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]
                                        for a,b,c,d in numcomb:
                                            if arrs[b] - arrs[a] == c:
                                                temp  += d
                                        ans=max(ans,temp)
print(ans)

Submission status: Accepted

Solution code:
N,M,Q=map(int,input().split())
from copy import copy
stack=[[1]]
A=[]
while stack:
    temp=stack.pop()
    if len(temp)==N:
        A.append(temp)
    else:
        x=temp[-1]
        for i in range(x,M+1):
            temp.append(i)
            stack.append(copy(temp))
            temp.pop()

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

L=len(A)
ans=0
for i in range(L):
    point=0
    for j in range(Q):
        if A[i][q[j][1]-1]-A[i][q[j][0]-1]==q[j][2]:
            point+=q[j][3]
    ans=max(ans,point)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
n,m,q = map(int,input().split())
ans = -1
li = [tuple(map(int,input().split())) for i in range(q)]
for K in combinations_with_replacement(range(1,m+1),n):
    s = 0
    for a,b,c,d in li:
        a -= 1
        b -= 1
        if K[b]-K[a] == c:
            s += d
    ans = max(ans,s)
print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m,q=map(int,input().split())
l=[list(map(int,input().split()))for i in range(q)]
y=0
for i in itertools.combinations_with_replacement(range(1,m+1),n):
 x=0
 for a,b,c,d in l:
  if i[b-1]-i[a-1]==c:x+=d
 y=max(y,x)
print(y)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

ans = 0
for c in combinations_with_replacement(range(1,m+1),n):
    v = 0
    for s in s_list:
        if c[s[1]-1] - c[s[0]-1] == s[2]:
            v+=s[3]
    
    ans = max(ans,v)
print(ans)

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
abcd=[list(map(int,input().split()))  for _ in range(q)]
A=[int(i) for i in range(1,m+1)]
from itertools import combinations_with_replacement
ans=0
for l in list(combinations_with_replacement(A,n)):
  t=0
  for a,b,c,d in abcd:
    if l[b-1]-l[a-1]==c:t+=d
  ans=max(t,ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M, Q = mapint()
abcd = [list(mapint()) for _ in range(Q)]

from itertools import combinations_with_replacement

lis = range(1, M+1)
ans = 0
for l in combinations_with_replacement(lis, N):
    tmp = 0
    for a, b, c, d in abcd:
        if l[b-1]-l[a-1]==c:
            tmp += d
    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
input = lambda: sys.stdin.readline().rstrip()

def main():
    n, m, q = map(int, input().split())
    comb = [list(map(int, input().split())) for _ in range(q)]
    max_ = 0
    for i in itertools.combinations_with_replacement(range(1,m+1), n):
        point = 0
        for j in comb:
            if i[j[1]-1] - i[j[0]-1] == j[2]:
                point += j[3]
        max_ = max(max_, point)
    print(max_)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

m_range = list(range(1, M+1))
max_point = 0
for array in combinations_with_replacement(m_range, N):
    point = 0
    for (a, b, c, d) in num_list:
        if array[b-1] - array[a-1] == c:
            point += d
    max_point = max(max_point, point)
print(max_point)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as R

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

print(max([sum((d if S[b-1] - S[a-1] == c else 0) for a,b,c,d in L) for S in R(range(1, M+1), N)]))

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as c

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

print(max([sum(d if S[b-1] - S[a-1] == c else 0 for a, b, c, d in L) for S in c(range(1, M+1), N)]))

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

print(max([sum(d if AN[b-1] - AN[a-1] == c else 0 for a, b, c, d in abcdn) for AN in combinations_with_replacement(range(1, M+1), N)]))