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 numpy as np
N,M,Q=map(int, input().split())
matrix=[]
for _ in range(Q):
    c=list(map(int, input().split()))
    matrix.append(c)
#matrix = np.array(matrix)
import itertools
ansscore = 0
combi = list(itertools.combinations_with_replacement(range(1,M+1),N))
for i in combi:
    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
    ansscore = score if score>ansscore else ansscore

print(ansscore)

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

Submission status: Accepted

Solution code:
from sys import stdin


def input():
    return stdin.readline().strip()


def main():
    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())
        a[i] -= 1
        b[i] -= 1

    ans = 0

    def dfs(seq):
        nonlocal ans
        if len(seq) == N:
            score = 0
            for i in range(Q):
                if seq[b[i]] - seq[a[i]] == c[i]:
                    score += d[i]
            ans = max(ans, score)
            return

        score = 0
        start = seq[-1] if seq else 1
        for n in range(start, M + 1):
            seq.append(n)
            dfs(seq)
            seq.pop()

    dfs([1])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

patterns = []
def dfs(a):
  if len(a) == N:
    patterns.append(a)
  else:
    for i in range(int(a[-1]), M+1):
   	  dfs(a+[i])

dfs(a=[1])
result = 0
for p in patterns:
  r = 0
  for q in Qs:
    if p[q[1]-1]-p[q[0]-1]==q[2]:
      r += q[3]
  #print(p, r)
  result = max([result, r])
print(result)

Submission status: Accepted

Solution code:
import itertools

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

Submission status: Accepted

Solution code:
from sys import stdin


def input():
    return stdin.readline().strip()


def main():
    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())
        a[i] -= 1
        b[i] -= 1

    ans = 0

    def dfs(seq):
        nonlocal ans
        if len(seq) == N:
            score = 0
            for i in range(Q):
                if seq[b[i]] - seq[a[i]] == c[i]:
                    score += d[i]
            ans = max(ans, score)
            return

        score = 0
        start = seq[-1] if seq else 1
        for n in range(start, M + 1):
            seq.append(n)
            dfs(seq)
            seq.pop()

    dfs([])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,M,Q = list(map(int, input().split()))
a = [0] * Q
b = [0] * Q
c = [0] * Q
d = [0] * Q
res = 0

def dfs(array):
  if(len(array) == N+1):
    global res
    p = 0

    for i in range(Q):
      # Abi - Aai = Ci を満たすようなi についてのdiの総和
      if(array[b[i]] - array[a[i]] == c[i]):
        p += d[i]
  
    res = max(p, res);

    return

  array.append(array[-1])
  while(array[-1] <= M):
    dfs(array[::])
    array[-1] += 1

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

dfs([1])

print(res)

Submission status: Accepted

Solution code:
import itertools

N,M,Q = map(int, raw_input().split())
ABCD = []
for i in range(Q):
    abcd = map(int, raw_input().split())
    ABCD.append(abcd)

S = []
def gen(seq, n):
    if n == N:
        S.append(seq)
        return
    tail = seq[-1]
    for x in range(tail, M+1):
        gen(seq+[x], n+1)

gen([1], 1)

ans = 0
for seq in S:
    m = 0
    for a,b,c,d in ABCD:
        if seq[b-1] - seq[a-1] == c: 
            m += d
    ans = max(ans, m)
print ans

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

A = np.array(list(itertools.combinations_with_replacement(range(1, M+1), N)))
s = np.zeros(len(A), np.int32)

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

print(s.max())

Submission status: Accepted

Solution code:

from itertools import combinations_with_replacement

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

    ans = 0
    # m+n_C_n で重複組み合わせで広義単調増加の数列を表現する(高々 20_C_10 \simeq 2 \times 10^5)
    for i in combinations_with_replacement(range(1, m+1), n-1):
        A = [1] + list(i) # A の最小値は必ず１なのでn-1個選んで端に１を足してる
        total = 0
        for abcd in abcd_l:
            # Python は  0-originだから−１に注意 A_b - A_a = c
            if A[abcd[1]-1] - A[abcd[0]-1] == abcd[2]:
                total += abcd[3]
        ans = max(ans, total)
    return ans

if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
import itertools

N, M, Q = map(int, input().split())
A, B, C, D = [[] for _ in range(4)]

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

res = 0
for lst in itertools.combinations_with_replacement(range(0, M), N):
    res = max(res, sum([D[i] for i in range(Q) if lst[B[i]] - lst[A[i]] == C[i]]))

print(res)

Submission status: Accepted

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

T = range(1,M+1)
K = list(combinations_with_replacement(T,N))

ans = 0
for line in K:
    total = 0
    for combi in A:
        if line[combi[1]-1] - line[combi[0]-1] == combi[2]:
            total += combi[3]
    ans = max(total,ans)

print(ans)

Submission status: Accepted

Solution code:
import copy
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 = [1]
ans = 0
def dfs(lis):
    if len(lis) == n+1:
        now = 0
        for i in range(q):
            if lis[b[i]] - lis[a[i]] == c[i]:
                now += d[i]
        global ans
        ans = max(now, ans)
        return 0
    lis.append(lis[-1])
    while lis[-1] <= m:
        newlis = copy.deepcopy(lis)
        dfs(newlis)
        lis[-1] += 1
dfs(A)
print(ans)

Submission status: Accepted

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

ans = 0
for A in itertools.combinations_with_replacement(range(1, M+1), N):
    score = 0
    for a, b, c, d in buff:
        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())
a_list = [list(map(int, input().split())) for _ in range(q)]

A_comb = itertools.combinations_with_replacement(range(1, m+1), n)

d_sum = 0
for comb in A_comb:
    d_sum_by_comb  = 0
    for aq in a_list:
        b = aq[1]
        a = aq[0]
        c = aq[2]
        d = aq[3]
        if comb[b-1] - comb[a-1] == c:
            d_sum_by_comb += d

    if d_sum < d_sum_by_comb:
        d_sum = d_sum_by_comb

print(d_sum)

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
ptn = []
for i in range(Q):
    a,b,c,d = map(int, input().split())
    ptn.append([a-1,b-1,c,d])
mx = 0
def calc(arr):
    if len(arr) == N:
        global mx
        tot = 0
        for i in range(Q):
            if arr[ptn[i][1]] - arr[ptn[i][0]] == ptn[i][2]:
                tot += ptn[i][3]
        mx = max(mx, tot)
        return
    for i in range(1,M+1):
        if i < arr[-1]: continue
        calc(arr+[i])
for i in range(1,M+1):
    calc([i])
print(mx)

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
S=[[0 for i in range(4)] for j in range(Q)]
for i in range(Q):
    inputS=list(map(int,input().split()))
    S[i][0]=inputS[0]
    S[i][1]=inputS[1]
    S[i][2]=inputS[2]
    S[i][3]=inputS[3]
S2=[]
maxNum=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):
                                        S2=[a,b,c,d,e,f,g,h,i,j]
                                        count=0
                                        for k in range(Q):
                                            if S2[S[k][1]-1]-S2[S[k][0]-1]==S[k][2]:
                                                count+=S[k][3]
                                        maxNum=max(maxNum,count)
                                       
    
print(maxNum)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

n, m, q = map(int, input().split())
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))
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_with_replacement(range(1, m+1), len(it)):
    cnt = 0
    for i in range(q):
        if x[nb[i]] - x[na[i]] == c[i]:
            cnt += d[i]
    if ans < cnt:
        ans = cnt
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

result = 0
for x in itertools.combinations_with_replacement(range(1, M + 1), N):
    temp = 0
    for a, b, c, d in A:
        if x[b - 1] - x[a - 1] == c:
            temp += d
    if temp > result:
        result = temp

print(result)

Submission status: Accepted

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

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

cl = []
def dfs(i):
    if len(i) == n:
        cl.append(i)
        return
    for j in range(i[-1], m+1):
        dfs(i + [j])


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


ans = 0
for cc in cl:
    tmp = 0
    for a,b,c,d in abcdl:
        if cc[b-1] - cc[a-1] == c:
            tmp += d
    # print(tmp)
    ans = max(tmp, ans)

print(ans)

Submission status: Accepted

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

A_N = [[i] for i in range(1, M+1)]
for i in range(N-1):
  a = []
  for j in range(len(A_N)):
    last = A_N[j][-1]
    for k in range(last, M+1):
      a.append(A_N[j] + [k])
  A_N = a

high_score = 0
for i in range(len(A_N)):
  A = A_N[i]
  score = 0
  for j in range(len(l)):
    aj, bj, cj, dj = l[j]
    if A[bj-1]-A[aj-1] == cj:
      score += dj
  high_score = max(high_score, score)

print(high_score)

Submission status: Accepted

Solution code:
import os
import sys
from itertools import permutations, product, combinations_with_replacement

def main():
	n,m,q = map(int, input().split())
	target = [list(map(int,input().split())) for _ in range(q)]
	max_value = 0	
	
	for v in combinations_with_replacement(range(1,m+1),n):
		result = 0
		for i in target:
			if v[i[1]-1] - v[i[0]-1] == i[2]:
				result += i[3]
			else:
				pass
		max_value =  max(result,max_value)

	print(max_value)

if __name__ == "__main__":
        main()

Submission status: Accepted

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


lst = []
nn,mm,qq = (int(x) for x in input().split())
for i in range(1,mm+1):#1
    for j in range(i,mm+1):#2
        for k in range(j,mm+1):#3
            for l in range(k,mm+1):#4
                for m in range(l,mm+1):#5
                    for n in range(m,mm+1):#6
                        for o in range(n,mm+1):
                            for p in range(o,mm+1):
                                for q in range(p,mm+1):
                                    for r in range(q,mm+1):
                                        lst.append([i,j,k,l,m,n,o,p,q,r])
qlst = []

for i in range(qq):
    qlst.append([int(x) for x in input().split()])
score = 0
for combo in lst:
    cur_score = 0
    for a,b,c,d in qlst:
        if combo[b-1] - combo[a-1] == c:
            cur_score += d
    score = max(score, cur_score)
print(score)

Submission status: Accepted

Solution code:
import itertools
n, m, q = [int(i) for i in input().split()]
sm = 0
abcd = [[int(j) for j in input().split()] for i in range(q)]
a = [i[0] for i in abcd]
b = [i[1] for i in abcd]
c = [i[2] for i in abcd]
d = [i[3] for i in abcd]

it = itertools.combinations_with_replacement(range(1, m+1), n)
ans = 0
for i in it:
    sum = 0
    for j in range(len(a)):
        if(i[b[j]-1] - i[a[j]-1] == c[j]):
            sum += d[j]
    ans = max(sum,ans)

print(ans)

Submission status: Accepted

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

A_N = [[i] for i in range(1, M+1)]
for i in range(N-1):
  a = []
  for j in range(len(A_N)):
    last = A_N[j][-1]
    for k in range(last, M+1):
      a.append(A_N[j] + [k])
  A_N = a

high_score = 0
for i in range(len(A_N)):
  A = A_N[i]
  score = 0
  for j in range(len(l)):
    aj, bj, cj, dj = l[j]
    if A[bj-1]-A[aj-1] == cj:
      score += dj
  if high_score < score:
    high_score = score 

print(high_score)

Submission status: Accepted

Solution code:
from sys import stdin


def input():
    return stdin.readline().strip()


def main():
    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())
        a[i] -= 1
        b[i] -= 1

    def dfs(seq, N, M):
        if len(seq) == N:
            score = 0
            for i in range(Q):
                if seq[b[i]] - seq[a[i]] == c[i]:
                    score += d[i]
            return score

        score = 0
        start = seq[-1] if seq else 1
        for n in range(start, M + 1):
            score = max(score, dfs(seq.copy() + [n], N, M))

        return score

    print(dfs([], N, M))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

from collections import deque

def dfs(min_val, length):
    if length == 0:
        return list([deque()])
    if min_val == m:
        return list([deque([m]) * length])
    ans = list()
    for i in range(min_val, m+1):
        remain = dfs(i, length-1)
        for j in remain:
            j.appendleft(i)
        ans.extend(remain)
    return ans

ans = 0
for i in dfs(1, n):
    tmp = 0
    for a, b, c, d in pairs:
        if (i[b-1] - i[a-1]) == c:
            tmp += d
    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
input = sys.stdin.buffer.readline
from itertools import combinations_with_replacement
def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
def RN(N): return [input().strip() for i in range(N)]


def main():
    N,M,Q = MI()
    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] = MI()
    dsum = 0
    max = 0

    l =list(combinations_with_replacement(range(1,M+1), N))
    for j in l:
        j = list(j)
        dsum = 0
        for k in range(Q):
            if j[b[k]-1]-j[a[k]-1] == c[k]:
                dsum += d[k]
        if max < dsum:
            max = dsum 
    print(max)




if __name__ == "__main__":
	main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

def main():
    N, M, Q = map(int, input().split())
    ABCD = [list(map(int, input().split())) for i in range(Q)]
    ans = 0

    for A in combinations_with_replacement(range(M), N):
        temp = 0
        for abcd in ABCD:
            if A[abcd[1]-1]+1 == A[abcd[0]-1]+1 + abcd[2]:
                temp += abcd[3]
        if temp > ans:
            ans = temp
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
N, M, Q = map(int, input().split(" "))
abcd = []
for i in range(Q):
    abcd.append(list(map(int, input().split(" "))))
A = list(itertools.combinations_with_replacement(range(1, M + 1), N))
ans = 0            
for a in A:
    score = 0
    for i in abcd:
        if a[i[1] - 1] == a[i[0] - 1] + i[2]:
            score += i[3]
    ans = max(ans, score)
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 A in combinations_with_replacement(range(M), N):
    temp = 0
    for abcd in ABCD:
        if A[abcd[1]-1]+1 == A[abcd[0]-1]+1 + abcd[2]:
            temp += abcd[3]
    if temp > ans:
        ans = temp
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
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())


sequences = []

def dfs(seq):
    if len(seq) == N+1:
        sequences.append(seq)
        return
    tail_num = seq[-1]
    for nxt_d in range(tail_num,M+1):
        dfs(seq+[nxt_d])
dfs([1])


ans = 0
for seq in sequences:
    score = 0
    for i in range(Q):
        if int(seq[b[i]]) - int(seq[a[i]]) == c[i]:
            score += d[i]
    ans = max(ans, score)
print(ans)




#     if len(seq) == N:
# TypeError: object of type 'NoneType' has no len()



# def dfs(s):
#     if len(s) == N:
#         sequences.append(s)
#         return
#     if s == '':
#         tail_num = 1
#     else:
#         tail_num = int(s[-1])
#     for nxt_d in range(tail_num,M+1):
#         dfs(s+str(nxt_d))
# dfs('')
## 10の時2桁追加されて停止条件飛び越す
## 10の時は0を追加して例外亭な処理する方針

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
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())


sequences = []

def dfs(seq):
    if len(seq) == N+1:
        sequences.append(seq)
        return
    tail_num = seq[-1]
    for nxt_d in range(tail_num,M+1):
        dfs(seq+[nxt_d])
dfs([1])


ans = 0
for seq in sequences:
    score = 0
    for i in range(Q):
        if int(seq[b[i]]) - int(seq[a[i]]) == c[i]:
            score += d[i]
    ans = max(ans, score)
print(ans)




#     if len(seq) == N:
# TypeError: object of type 'NoneType' has no len()



# def dfs(s):
#     if len(s) == N:
#         sequences.append(s)
#         return
#     if s == '':
#         tail_num = 1
#     else:
#         tail_num = int(s[-1])
#     for nxt_d in range(tail_num,M+1):
#         dfs(s+str(nxt_d))
# dfs('')
## 10の時2桁追加されて停止条件飛び越す
## 10の時は0を追加して例外亭な処理する方針

Submission status: Accepted

Solution code:
def main():
    from itertools import combinations_with_replacement
    import sys
    input = sys.stdin.buffer.readline
    N, M, Q = (int(i) for i in input().split())
    T = [[int(i) for i in input().split()] for j in range(Q)]
    ans = 0
    for C in combinations_with_replacement(range(1, M+1), N):
        A = sorted(C)
        cur = 0
        for a, b, c, d in T:
            if A[b-1] - A[a-1] == c:
                cur += d
        ans = max(ans, cur)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
N, M, Q = map(int, input().split(" "))
abcd = []
for i in range(Q):
    abcd.append(list(map(int, input().split(" "))))
q = deque([[i] for i in range(1, M + 1)])
A = []
while q:
    tmp = q.pop()
    if len(tmp) == N:
        A.append(tmp)
    else:
        for i in range(tmp[-1], M + 1):
            tmp_copy = tmp.copy()
            tmp_copy.append(i)
            q.append(tmp_copy)
ans = 0            
for a in A:
    score = 0
    for i in abcd:
        if a[i[1] - 1] == a[i[0] - 1] + i[2]:
            score += i[3]
    ans = max(ans, score)
print(ans)

Submission status: Accepted

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

def sum_d(l):
    s = 0
    
    for a,b,c,d in score_list:
        if (l[b-1] - l[a-1])==c:
            s += d
    return s

def f(l,ans):
    if(len(l)==n):
        return sum_d(l)

    if(len(l)==0):
        num=1
    else:
        num=l[-1]

    while(num <= m):
        ret = f(l+[num],ans)
        if(ans < ret):
            ans = ret
        num += 1

    return ans

ans = f([],ans=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 x in combinations_with_replacement(range(M), N):
    temp = 0
    for i in range(Q):
        if x[ABCD[i][1]-1]+1 == x[ABCD[i][0]-1]+1 + ABCD[i][2]:
            temp += ABCD[i][3]
    if temp > ans:
        ans = temp
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,m,q=map(int,input().split())
abcd=[list(map(int,input().split())) for _ in range(q)]
ans=0
s,seq=[],[]
def dfs(s):
    if len(s)==n:
        seq.append(s)
        return
    for i in range(1,m+1):
        if s:
            if s[-1]<=i:
                dfs(s+[i])
        else:
            dfs(s+[i])
dfs(s)
#print(seq)
for s in seq:
    cand=0
    for a,b,c,d in abcd:
        a-=1
        b-=1
        if s[b]-s[a]==c:
            cand+=d
    ans=max(ans,cand)
print(ans)

Submission status: Accepted

Solution code:
import itertools
n, m, q = map(int, input().strip().split())
L = [list(map(int, input().split())) for _ in range(q)]
ans=0
for possibleA in itertools.combinations_with_replacement(range(1,m+1),n):
    di_total=0
    for a,b,c,d in L:
        if possibleA[b-1]-possibleA[a-1]==c:
            di_total+=d
    ans=max(ans,di_total)
print(ans)

Submission status: Accepted

Solution code:
def dfs(nums, length, min_lim):
# numsは数列の本体、lengthは数字の何個目まで決めたか、min_limは次の数字の最小値
    ans = 0
    if length == n:
    # 数列が完成したので、得点を計算します
        score_ret = 0
        for a, b, c, d in req:
            # nums[0]を捨てたので、nums[b-1]...としなくて済みます
            if nums[b] - nums[a] == c:  
                score_ret += d
        return score_ret  # この数列の得点を返します
    else:
        # まだ数列が完成していません
        for nu in range(min_lim, m + 1):
        # 次の数字の下限はmin_limで、上限はmです
            new_nums = nums + [nu]  # 長さ1のリスト[nu]を連結します
            # lengthは1増えて、次の下限は今付け加えた数字nuです
            score = dfs(new_nums, length + 1, nu)
            ans = max(ans, score) # 最大の得点を更新します

    # すべてが終わったので、答えを返します
    return ans


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

# 問題文のa,b,c,dのリストreqです。[[a1,b1,c1,d1],[a2,b2,c2,d2],[a3,b3,c3,d3]]のようになります。
req = [list(map(int, input().split())) for _ in range(q)]

# 最終的に答えが返ってくるようにします。処理はすべてdfsメソッドでやってもらいます。
# 数列の番号と添字を一致させたいので、長さ1のリストを最初の状態にしておきます。
# サンプル1の数列は[-1, 1, 3, 4]になります。
ans = dfs([-1], 0, 1)
print(ans)

Submission status: Accepted

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

mx = 0
a = [1]*10

for s1 in range(1, M+1):
    a[0] = s1
    for s2 in range(s1, M+1):
        a[1] = s2
        for s3 in range(s2, M+1):
            a[2] = s3
            for s4 in range(s3, M+1):
                a[3] = s4
                for s5 in range(s4, M+1):
                    a[4] = s5
                    for s6 in range(s5, M+1):
                        a[5] = s6
                        for s7 in range(s6, M+1):
                            a[6] = s7
                            for s8 in range(s7, M+1):
                                a[7] = s8
                                for s9 in range(s8, M+1):
                                    a[8] = s9
                                    for s10 in range(s9, M+1):
                                        a[9] = s10
                                        
                                        cnt = 0
                                        for i in range(Q):
                                            si = s[i]
                                            if a[si[1]-1] - a[si[0]-1] == si[2]:
                                                cnt += si[3]
                                            mx = max(mx, cnt)
                                            
print(mx)

Submission status: Accepted

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

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

print(max(sum(d for a, b, c, d in T if l[b] - l[a] == c) for l in L))

Submission status: Accepted

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

ans = 0

def calc(LL):
    global n,m,q,D,ans
    ret = 0
    for dd in D:
        a,b,c,d = dd[0],dd[1],dd[2],dd[3]
        if LL[b-1]-LL[a-1] == c:
            ret += d
    ans = max(ans,ret)

def func(LL):
    global n,m
    if len(LL) >= n:
        return calc(LL)
    for i in range(LL[-1],m+1):
        func(LL+[i])

n,m,q = map(int,input().split())
D = [list(map(int,input().split())) for _ in range(q)]
for i in range(1,m+1):
    func([i])
print(ans)

Submission status: Accepted

Solution code:
N, M, Q = list(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)

listA = list(range(1,N+1))
ANS = 0

import itertools
for i in itertools.combinations_with_replacement(range(1,M+1), N):
    f = 0
    for j in range(len(i)-1):
        if not i[j] <= i[j+1]:
            f=1
    if f == 0:
        #print(i)
        ans = 0
        for q in range(Q):
            if i[B[q]-1] - i[A[q]-1] == C[q]:
                ans += D[q]
        ANS = max([ANS, ans])
print(ANS)
#print(ANS)

Submission status: Accepted

Solution code:
import itertools
import copy
  
N,M,Q = map(int, input().split())
a = [0]*Q
b = [0]*Q
c = [0]*Q
d = [0]*Q

now = 0
ans = 0

for i in range(Q):
  a[i],b[i],c[i],d[i] = map(int, input().split())
  
def dfs(A):
#  print('input',A)
  global ans
  if (len(A) == N):
    now = 0
    for i in range(Q):
      if A[b[i]-1] - A[a[i]-1] == c[i]:
        now += d[i]
    ans = max(now,ans)
    return
  if len(A) == 0:
    A=[1]
  else:
    A.append(A[-1])

  while A[-1] <= M:
#    print('mid',A,A[-1])
    dfs(copy.deepcopy(A))
    A[-1] +=1
  
  
dfs(list([1]))  
print(ans)

Submission status: Accepted

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest
import itertools

sys.setrecursionlimit(500*500)

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    n,m,q=map(int, readline().rstrip().split())

    aa=[0]*q
    bb=[0]*q
    cc=[0]*q
    dd=[0]*q

    for i in range(q):
        aa[i],bb[i],cc[i],dd[i]=map(int, readline().rstrip().split())

    max_score=0

    for a in itertools.combinations_with_replacement(list(range(1,m+1)),n):
        score=0
        for i in range(q):
            if (a[bb[i]-1]-a[aa[i]-1])==cc[i]:
                score+=dd[i]
        max_score=max(max_score,score)

    print(max_score)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()


### ----------------
### ここまで 
### ----------------