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: Time Limit Exceeded

Solution code:
import itertools
N, M, Q = map(int, input().split())
List = [list(map(int, input().split())) for i in range(Q)]
Max = 0

for a in itertools.combinations_with_replacement(range(1, M+1), N):
  A = list(a)
  A.sort()
  point = 0
  for i in range(Q):
    ai = List[i][0]
    bi = List[i][1]
    if 1 <= ai <= N and 1 <= bi <= N:
      if A[bi-1]-A[ai-1] == List[i][2]:
        point += List[i][3]
    if Max < point:
      Max = point

print(Max)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations_with_replacement
n,m,q=map(int,input().split())
l=list(combinations_with_replacement(range(1,m+1),n))

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

for j in range(len(l)):
    tmp=0
    for i in range(len(lt)):
        a,b,c,d = lt[i][0],lt[i][1],lt[i][2],lt[i][3]
        if l[j][b-1]-l[j][a-1] == c:
            tmp += d
    res=max(tmp,res)

print(res)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import combinations_with_replacement
N, M, Q = map(int, input().split())
# N, M, Q = 4, 6, 10

Qi = np.zeros((Q, 4))

# listSample = []
# listSample.append("2 4 1 86568")
# listSample.append("1 4 0 90629")
# listSample.append("2 3 0 90310")
# listSample.append("3 4 1 29211")
# listSample.append("3 4 3 78537")
# listSample.append("3 4 2 8580")
# listSample.append("1 2 1 96263")
# listSample.append("1 4 2 2156")
# listSample.append("1 2 0 94325")
# listSample.append("1 4 3 94328")



for i in range(Q):
    Qi[i][0], Qi[i][1], Qi[i][2], Qi[i][3] = map(int,input().split())
    
# for i in range(Q):
    # Qi[i][0], Qi[i][1], Qi[i][2], Qi[i][3] = map(int,listSample[i].split())

# Qi[0][0], Qi[0][1], Qi[0][2], Qi[0][3] = map(int,"1 3 3 100".split())
# Qi[1][0], Qi[1][1], Qi[1][2], Qi[1][3] = map(int,"1 2 2 10".split())
# Qi[2][0], Qi[2][1], Qi[2][2], Qi[2][3] = map(int,"2 3 2 10".split())


Mi = np.arange(1, M+1)
maxD = 0
for listMi in (list(combinations_with_replacement(Mi, N))):
    d = 0
    for i in range(Q):
        if (int(listMi[int(Qi[i][1]-1)]-listMi[int(Qi[i][0]-1)]) == int(Qi[i][2])):
            d += Qi[i][3]
    if d>maxD:
        maxD = d
print (int(maxD))

Submission status: Time Limit Exceeded

Solution code:
import itertools
N, M, Q = map(int, input().split())
l = []
for _ in range(Q):
    l.append(tuple(map(int, input().split())))
    
c = list(itertools.combinations(list(range(1, M+1))*Q, N))

max = 0
for i in c:
    i = list(i)
    i.sort()
    sum = 0
    for j in l:
        if i[j[1]-1] - i[j[0]-1] == j[2]:
            sum += j[3]
    if max < sum:
        max = sum
        
print(max)

Submission status: Time Limit Exceeded

Solution code:
def ite(N, M):
    import itertools
    li = []
    for i in range(1, M+1, 1):
         li.extend([i for _ in range(N)])
         
    p = itertools.permutations(li, N)
    return list(p)


def check(li):
    for i in range(len(li)-1):
        if li[i] > li[i+1]:
            return False
    return True
    
def score(l1, l2):
    s = 0
    for (a, b, c, d) in l2:
      if l1[b-1] - l1[a-1] == c:
            s += d
    return s
        

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

m_s = 0
li2 = ite(N, M) 
for l2 in li2:
    if check(l2):
        s = score(l2, li)
        if m_s < s:
            m_s = s
            
print(m_s)

Submission status: Time Limit Exceeded

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

import itertools

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

ans = 0
cnt = 0
X = [i for i in range(1, M+1)]
Y = X * N
lis_2 = []

for i in itertools.combinations_with_replacement(Y, r=N):
    cnt = 0
    j = list(i)
    j.sort()
    for k in lis:
        if j[k[1]-1] - j[k[0]-1] == k[2]:
            cnt += k[3]
    ans = max(ans, cnt)

print(ans)

Submission status: Time Limit Exceeded

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

def calc(an, qn):
    sum = 0
    for q in qn:
        a = q[0]-1
        b = q[1]-1
        c = q[2]
        d = q[3]
        if an[b] - an[a] == c:
            sum += d
    return sum

an = set()
nums = list(range(1,m+1))
for a in itertools.product(nums, repeat=n):
    an.add(tuple(sorted(a)))

max_d = 0
for a in an:
    d = calc(a, qn)
    max_d = max(max_d, d)

print(max_d)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

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

a = np.array([],dtype = 'int64')
b = np.array([],dtype = 'int64')
c = np.array([],dtype = 'int64')
d = np.array([],dtype = 'int64')

for i in range(q):
    ai,bi,ci,di = map(int,input().split())
    a = np.append(a,ai)
    b = np.append(b,bi)
    c = np.append(c,ci)
    d = np.append(d,di)

nums = np.arange(1,m+1)
ans = 0
for balls in itertools.combinations_with_replacement(nums,n):
    tempans = 0
    for j in range(q):
        if(balls[b[j]-1] - balls[a[j]-1] == c[j]):
            #print(balls[b[j]-1],balls[a[j]-1],c[j])
            tempans = tempans + d[j]
    ans = max(ans,tempans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]
abcd = sorted(abcd, key=lambda x:x[3], reverse=True)
A = [0]*N
a = 0
for i in range(2**Q):
  bag = []
  A = [-1]*(N+1)
  A[1] = 1
  ans = 0
  for j in range(Q):
    if (i>>j)&1:
      bag += [j]

  for j in bag:
    if A[abcd[j][1]] == -1:
      if A[abcd[j][0]] + abcd[j][2] <= M:
        A[abcd[j][1]] = A[abcd[j][0]] + abcd[j][2]
        ans += abcd[j][3]
      else:
        ans = 0
        break
    elif A[abcd[j][1]] == A[abcd[j][0]] + abcd[j][2]:
      ans += abcd[j][3]
    else:
      ans = 0
      break

  a = max(ans, a)

print(a)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, m, q = map(int, input().split())
abcd_lis = []
for i in range(q):
    abcd = list(map(int, input().split()))
    abcd_lis.append(abcd)
L = []
for i in range(1, m+1):
    L.append(i)
H = list(itertools.combinations_with_replacement(L, n))
max_score = 0
for h in H:
    score = 0
    for j in range(q):
        if list(h)[abcd_lis[j][1]-1]-list(h)[abcd_lis[j][0]-1] == abcd_lis[j][2]:
            score += abcd_lis[j][3]
    if score > max_score:
        max_score = score
print(max_score)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from collections import defaultdict
    sys.setrecursionlimit(10 ** 6)
    input = sys.stdin.readline
    N, M, Q = [int(x) for x in input().strip().split()]
    abcd = [0] * Q
    for q in range(Q):
        abcd[q] = [int(x) for x in input().strip().split()]

    abcd.sort(key=lambda x:(x[0],x[1]))
    ans = 0
    for i in range(1, 2 ** Q):
        vec = [1] * N
        flag = [False] * N
        ans_ = 0
        for q in range(Q):
            # print((i >> q) % 2, end='')
            if (i >> q) % 2 == 0:
                continue
            a, b, c, d = abcd[q]
            if not flag[b-1]:
                if vec[a-1] + c > M:
                    break
                vec[b-1] = vec[a-1] + c
                ans_ += d
                flag[b-1] = True
                flag[a-1] = True
            elif vec[b-1] - vec[a-1] == c:
                ans_ += d
            else:
                break
        
        if vec != sorted(vec):
            continue
            
        ans = max(ans, ans_)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

import itertools

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

ans = 0
cnt = 0
X = [i for i in range(1, M+1)]
Y = X * N
lis_2 = []

for i in itertools.permutations(Y, r=N):
    cnt = 0
    j = list(i)
    j.sort()
    if j in lis_2:
        continue
    for k in lis:
        if j[k[1]-1] - j[k[0]-1] == k[2]:
            cnt += k[3]
    ans = max(ans, cnt)
    lis_2.append(j)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from collections import defaultdict
    sys.setrecursionlimit(10 ** 6)
    input = sys.stdin.readline
    N, M, Q = [int(x) for x in input().strip().split()]
    abcd = [0] * Q
    for q in range(Q):
        abcd[q] = [int(x) for x in input().strip().split()]

    abcd.sort(key=lambda x:(x[0],x[1]))
    ans = 0
    for i in range(1, 2 ** Q):
        vec = [1] * N
        flag = [False] * N
        ans_ = 0
        for q in range(Q):
            # print((i >> q) % 2, end='')
            if (i >> q) % 2 == 0:
                continue
            a, b, c, d = abcd[q]
            if not flag[b-1]:
                if vec[a-1] + c > M:
                    break
                vec[b-1] = vec[a-1] + c
                ans_ += d
                flag[b-1] = True
                flag[a-1] = True
            elif vec[b-1] - vec[a-1] == c:
                ans_ += d
            else:
                break
        
        if vec != sorted(vec):
            continue
            
        # print(bin(i), vec, ans_)
        if ans_ == 448129:
            print('★')
        ans = max(ans, ans_)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,M,Q=map(int, input().split())
matrix=[]
for _ in range(Q):
    c=list(map(int, input().split()))
    matrix.append(c)
import itertools
scorelist=[]
for i in itertools.product(range(1,M+1), repeat=N):
    i = list(i)
    i.sort()
    score=0
    for l in matrix:
        a=l[0]
        b=l[1]
        c=l[2]
        d=l[3]
        if i[b-1]-i[a-1]==c:
            score+=d
    scorelist.append(score)
print(max(scorelist))

Submission status: Time Limit Exceeded

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

import itertools

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

ans = 0
cnt = 0
X = [i for i in range(1, M+1)]
Y = X * N

for i in itertools.permutations(Y, r=N):
    cnt = 0
    j = list(i)
    j.sort()
    for k in lis:
        if j[k[1]-1] - j[k[0]-1] == k[2]:
            cnt += k[3]
    ans = max(ans, cnt)

print(ans)

Submission status: Time Limit Exceeded

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
ans = 0
for i in range(2 ** q):
    flg = [False] * q
    for j in range(q):
        if i >> j & 1:
            flg[j] = True
    flg2 = True
    val = 0
    lis = [0] * n
    lis2 = [True] * n
    for i in range(q):
        if flg[i] == True:
            if lis2[b[i]] == True:
                val += d[i]
                lis[b[i]] = lis[a[i]] + c[i]
                lis2[a[i]] = False
                lis2[b[i]] = False
            elif lis[b[i]] - lis[a[i]] == c[i]:
                val += d[i]
            else:
                flg2 = False
    for i in range(1,n):
        if lis[i] < lis[i-1]:
            flg2 = False
    if flg2 == True:
        ans = max(ans,val)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))

n, m, q = map(int, input().split())
vec = []
a = []
b = []
c = []
d = []
for _ in range(q):
    i, j, k, l = map(int, input().split())
    a.append(i - 1)
    b.append(j - 1)
    c.append(k)
    d.append(l)
it = a + b
it = list(set(it))
for i in range(1, m+1):
    for j in range(len(it)):
        vec.append(i)
na = []
nb = []
for i in range(q):
    for j in range(len(it)):
        if a[i] == it[j]:
            na.append(j)
        if b[i] == it[j]:
            nb.append(j)
ans = 0
for x in combinations(vec, len(it)):
    cnt = 0
    for i in range(q):
        if x[nb[i]] - x[na[i]] == c[i]:
            cnt += d[i]
    #print(x, cnt)
    if ans < cnt:
        ans = cnt
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
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())

ans = 0
for i in range(2 ** q):
    score = [0] * n
    flag = True
    cnt = 0
    for j in range(q):
        if i >> j & 1:
            score[b[j] - 1] = score[a[j] - 1] + c[j]
            cnt += d[j]
    for j in range(q):
        if i >> j & 1:
            if score[b[j] - 1] - score[a[j] - 1] != c[j]:
                flag = False
                break
    if flag == True:
        ans = max(ans, cnt)

print(ans)

Submission status: Time Limit Exceeded

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 check(num):
    num = list(str(num))
    res = 0
    for a,b,c,d in abcd:
        if int(num[b-1]) - int(num[a-1]) == c:
            res += d
    return res

n,m,q = LI()
abcd = [LI() for _ in range(q)]
que = deque()
que.append(1)
ans = 0
f = defaultdict(int)
while que:
    fig = que.popleft()
    if len(str(fig)) <= n+1:
        num = int(str(fig)[-1])
        for i in range(num, m+1):
            que.append(int(str(fig)+str(i)))
    else:
        ans = max(ans, check(fig))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,m,q=map(int,input().split())
l=[list(map(int,input().split())) for i in range(q)] 
u=[]
for i in range(1,m+1):
  for k in range(n):
    u.append(i)
a=list(itertools.combinations(u,n))
ans=[]

for i in range(len(a)):
  c=0
  for k in range(len(l)):
    if a[i][l[k][1]-1]-a[i][l[k][0]-1]==l[k][2]:
      c+=l[k][3]
  ans.append(c)
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
n, m, q = map(int, input().split())
l = [[*map(int, input().split())] for _ in range(q)]
res = 0
for x in product(*[range(m) for _ in range(n)]):
    if list(x) != sorted(x): continue
    score = 0
    for a, b, c, d in l:
        if x[b - 1] == x[a - 1] + c:
            score += d
    res = max(res, score)
print(res)

Submission status: Time Limit Exceeded

Solution code:
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.append(a - 1)
    B.append(b - 1)
    C.append(c)
    D.append(d)

L = []

def f(l):
    if len(l) == n:
        L.append(l)
        return
    for i in range(l[-1], m + 1):
        f(l + [i])

for i in range(1, m + 1):
    f([1])

ans = 0

for l in L:
    ans = max(ans, sum(d for a, b, c, d in zip(A, B, C, D) if l[b] - l[a] == c))

print(ans)

Submission status: Time Limit Exceeded

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

nums = []
for i in range(m):
    tmp = [i + 1] * n
    nums.extend(tmp)
ans = 0
for comb in itertools.combinations(nums, n):
    tmp = 0
    for a, b, c, d in values:
        if comb[b - 1] - comb[a - 1] == c: tmp += d
    ans = max(tmp, ans)
print(ans)

Submission status: Time Limit Exceeded

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

max_score = 0
for p in itertools.product(range(1, m + 1), repeat=n):
    if any(p[i] > p[i + 1] for i in range(n - 1)):
        continue
    score = 0
    for a, b, c, d in queries:
        if p[b - 1] - p[a - 1] == c:
            score += d
    max_score = max(score, max_score)
print(max_score)

Submission status: Accepted

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

def dfs(L: list):
    global res
    A = L[::]
    if len(A) == N + 1:
        now = 0
        for i in range(Q):
            if A[b[i]] - A[a[i]] == c[i]:
                now += d[i]
        res = max(res, now)
        # print(A, now)
        return
    
    A.append(A[-1])
    while A[-1] <= M:
        dfs(A)
        A[-1] += 1
    
a, b, c, d = [], [], [], []
for _ in range(Q):
    _a, _b, _c, _d = map(int, input().split())
    a.append(_a)
    b.append(_b)
    c.append(_c)
    d.append(_d)

dfs([1])
print(res)

Submission status: Accepted

Solution code:
# 参考 : https://atcoder.jp/contests/abc165/submissions/16921279
# 参考 : https://atcoder.jp/contests/abc165/submissions/16832189
from collections import deque
n,m,q = map(int,input().split())
l = [list(map(int,input().split())) for i in range(q)]
a,b,c,d = [list(i) for i in zip(*l)]
# 数列 A の基(最初は1を入れておく)
queue = deque([[1]])
ans = 0
# 数列 A の候補がなくなる(キューが空になる)まで探索
while queue:
    # 数列 A を前から一つ取り出す
    x = queue.popleft()
    # 数列 A が長さ N か
    if len(x) == n:
        s = 0
        # 実際に何点取得できるか
        for i in range(q):
            if x[b[i]-1] - x[a[i]-1] == c[i]:
                s += d[i]
        ans = max(ans,s)
    else:
        # 違う場合、後ろに数字を付け足す
        # 付け足す数字は取り出した数列 A の一番後ろの値から M まで
        # 最終的に長さが 1 , 2 ... N となり、if の条件を満たすようになる
        for j in range(x[-1],m+1):
            y = x + [j]
            queue.append(y)
print(ans)
# 制約
# 2 <= N <= 10
# 1 <= M <= 50
# 1 <= Q <= 50
# なのでこの探索は間に合う
# 入力例 1 は A[1,3,4]
# 入力例 2 は A[1,1,1,4]
# 入力例 3 は A[1,1,1,1,1,1,1,1,1,10]
# が最大得点となる

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())
s = [1]*n
mx = 0
while True:
  sc = 0
  for i in range(q):
    if s[b[i]-1]-s[a[i]-1] == c[i]:
      sc += d[i]
  mx = max(mx,sc)
  s[n-1] += 1
  if s[n-1]>m:
    s[n-2]+=1
    for k in range(n-2):
      if s[n-k-2]>m:
        s[n-k-3]+=1
    for i in range(1,n):
      if s[i]>m:
        s[i]=s[i-1]
  if s[0]>m:
    break
print(mx)

Submission status: Accepted

Solution code:
N,M,Q = map(int,input().split())
abcd_array = []
for i in range(Q):
    abcd = list(map(int,input().split()))
    abcd_array.append(abcd)
max_point = 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):
                                    As = [1,a,b,c,d,e,f,g,h,i]
                                    point = 0
                                    for j in range(Q):
                                        if As[abcd_array[j][1]-1] - As[abcd_array[j][0]-1] == abcd_array[j][2]:
                                            point += abcd_array[j][3]
                                        if j == Q-1 and max_point < point:
                                            max_point = point
print(max_point)

Submission status: Accepted

Solution code:
from collections import deque

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

ptn = deque([])
for i in range(M):
  ptn.append([i])
while len(ptn) > 0:
  p = ptn.pop()
  if len(p) < N:
    for i in range(p[-1], M):
      ptn.append(p+[i])
  else:
    patterns.append(p)
answer = 0
for p in patterns:
  point = 0
  for a, b, c, d in queries:
    if p[b-1]-p[a-1] == c:
      point += d
  answer = max(answer, point)
print(answer)

Submission status: Accepted

Solution code:
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.append(a-1)
  B.append(b-1)
  C.append(c)
  D.append(d)
  
from collections import deque
que = deque([[1]])
M = 0

while que:
  
  lst = que.popleft()
  if len(lst) == n:
    s = 0
    for i in range(q):
      if lst[B[i]] - lst[A[i]] == C[i]:
        s += D[i]
    if M < s:
      M = s
      
  else:    
    for j in range(lst[-1],m+1):
      lst2 = lst +[j]
      que.append(lst2)
    
print(M)

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())

from itertools import combinations_with_replacement as comb_rplc
answer = 0

for seq in comb_rplc(range(1,M+1),N):
    candi = 0
    
    for i in range(Q):
        if seq[B[i]-1]-seq[A[i]-1] == C[i]:
            candi += D[i]
    answer = max(candi,answer)
print(answer)

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):
  a[i],b[i],c[i],d[i]=map(int,input().split())
l=range(1,M+1)

i=0;D=[]
for v in itertools.combinations_with_replacement(l, N):
  D.append(0)
  for j in range(Q):
    if v[b[j]-1]-v[a[j]-1]==c[j]:
      D[i]+=d[j]
  i+=1
print(max(D))

Submission status: Accepted

Solution code:
import itertools
from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom
  
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())
l=range(1,M+1)


h=combinations_count(M+N-1, N)
H=[0]*h;i=0
for v in itertools.combinations_with_replacement(l, N):
    H[i]=v
    i+=1

D=[0 for j in range(h)]

for i in range(h):
  for j in range(Q):
    if H[i][b[j]-1]-H[i][a[j]-1]==c[j]:
      D[i]+=d[j]
  
print(max(D))

Submission status: Accepted

Solution code:
import sys
import itertools

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.append(a)
    B.append(b)
    C.append(c)
    D.append(d)

num = list(range(1,M+1))
ans = 0
for tpl in itertools.combinations_with_replacement(num,N):
    point = 0
    for i in range(Q):
        if tpl[B[i]-1] - tpl[A[i]-1] == C[i]:
            point += D[i]
    
    ans = max(ans,point)

print(ans)

Submission status: Accepted

Solution code:
import copy

def gen_mono_inc_seqs(N, M, cur_list, cur_len):
    if cur_len == N:
        return cur_list

    result = []
    for l in cur_list:
        last_val = l[len(l)-1]
        for i in range(last_val, M+1):
            tmp = copy.copy(l)
            tmp.append(i)
            result.append(tmp)

    return gen_mono_inc_seqs(N, M, result, cur_len+1)


def mono_inc_seqs(N, M):
    l = [ [i] for i in range(1, M+1) ]
    return gen_mono_inc_seqs(N, M, l, 1)

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_, b_, c_, d_ = map(int, input().split())
    a[i], b[i], c[i], d[i] = a_, b_, c_, d_

max_result = -1
seqs = mono_inc_seqs(N, M)
for seq in seqs:
    tmp = 0
    for i in range(Q):
        if seq[b[i]-1] - seq[a[i]-1] == c[i]:
            tmp += d[i]
    max_result = max(max_result, tmp)

print(max_result)

Submission status: Accepted

Solution code:
import sys

n,m,q = map(int,input().split())
score = {}
for i in range(1,10):
  for j in range(2,11):
    score[(i,j)] = [0 for k in range(10)]
    
for i in range(q):
  a,b,c,d = map(int,input().split())
  score[(a,b)][c] = d


total = []
dic = {}
for i in range(m):
  dic[(i,)] = score[(1,2)][i]
total.append(dic)

if n == 2:
  print(max(score[(1,2)]))
  sys.exit()

M = []
for i in range(2,n):
  Max = 0
  d = {}
  for k in range(m):
    for tup in total[-1].keys():
      s = total[-1][tup]
      if tup[-1] <= k:
        for j in range(1,i):
          s += score[(j+1,i+1)][k-tup[j-1]] 
        s += score[(1,i+1)][k]  
        ky = tup + (k,)
        d[ky] = s
        if s > Max:
          Max = s
  total.append(d)
  M.append(Max)

print(M[-1])

Submission status: Accepted

Solution code:
#
# abc165 c
#
import sys
from io import StringIO
import unittest
sys.setrecursionlimit(100000)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 4 3
1 3 3 100
1 2 2 10
2 3 2 10"""
        output = """110"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """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"""
        output = """357500"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """10 10 1
1 10 9 1"""
        output = """1"""
        self.assertIO(input, output)


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

    print(dfs([1]))


def dfs(L):
    if len(L) == N:
        score = 0
        for abcd in ABCD:
            a, b, c, d = abcd
            if L[b-1] - L[a-1] == c:
                score += d
        return score

    ans = 0
    for i in range(L[-1], M+1):
        NL = L + [i]
        ans = max(ans, dfs(NL))

    return ans


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:
#
# abc165 c
#
import sys
from io import StringIO
import unittest
sys.setrecursionlimit(100000)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 4 3
1 3 3 100
1 2 2 10
2 3 2 10"""
        output = """110"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """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"""
        output = """357500"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """10 10 1
1 10 9 1"""
        output = """1"""
        self.assertIO(input, output)


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

    T = []
    func([1], T)

    ans = 0
    for t in T:
        score = 0
        for abcd in ABCD:
            a, b, c, d = abcd
            if t[b-1] - t[a-1] == c:
                score += d
        ans = max(ans, score)
    print(ans)


def func(L, T):
    if len(L) == N:
        T.append(L)
        return

    for i in range(L[-1], M+1):
        NL = L + [i]
        func(NL, T)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:
#
# abc165 c
#
from itertools import combinations_with_replacement as cwr
import sys
from io import StringIO
import unittest
sys.setrecursionlimit(100000)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 4 3
1 3 3 100
1 2 2 10
2 3 2 10"""
        output = """110"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """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"""
        output = """357500"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """10 10 1
1 10 9 1"""
        output = """1"""
        self.assertIO(input, output)


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

    T = []
    func([1], T)

    ans = 0
    for t in cwr(range(1, M+1), N):
        score = 0
        for abcd in ABCD:
            a, b, c, d = abcd
            if t[b-1] - t[a-1] == c:
                score += d
        ans = max(ans, score)
    print(ans)


def func(L, T):
    if len(L) == N:
        T.append(L)
        return

    for i in range(L[-1], M+1):
        NL = L + [i]
        func(NL, T)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as cwr
[N, M, Q] = [int(i) for i in input().split()]
req = [list(map(int, input().split())) for _ in range(Q)]

ans = 0
for seq in cwr(range(1, M+1), N):
    sco = 0
    for i in range(Q):
        if seq[req[i][1]-1] - seq[req[i][0]-1] == req[i][2]:
            sco += req[i][3]
    s = max(ans, sco)
    ans = s
print(ans)

Submission status: Accepted

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

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

def gen():
    seq = [[1]]
    for _ in range(N-1):
        new_seq = []
        for prefix in seq:
            for i in range(prefix[-1], M+1):
                new_seq.append(prefix+[i])
        seq = new_seq
    return seq

ans = 0
for A in gen():
    cand = 0
    for a, b, c, d in rules:
        if A[b]-A[a] == c:
            cand += d
    ans = max(ans, cand)
print(ans)