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, Q = map(int, input().split())
X = []
for _ in range(Q):
    a, b, c, d = map(int, input().split())
    X.append((a, b, c, d))

def calc(L):
    s = 0
    for a, b, c, d in X:
        if L[b] - L[a] == c: s += d
    return s

def rec(L):
    if len(L) == N + 1:
        return calc(L)
    ma = 0
    for i in range(L[-1], M+1):
        ma = max(ma, rec(L + [i]))
    return ma

print(rec([1]))

Submission status: Accepted

Solution code:
def my_f(l, lq, q):
  p=0
  for i in range(q):
    if l[lq[i][1]-1]-l[lq[i][0]-1]==lq[i][2]:
      p+=lq[i][3]
  return p
  
n,m,q = (int(x) for x in input().split())

pmax = 0

lq=[]
for i in range(q):
  lq.append(list(map(int, input().split())))
  
l=[0]*10
while l[0] < m:
  l[0]+=1
  l[1]=l[0]-1
  while l[1] < m:
    l[1]+=1
    l[2]=l[1]-1
    while l[2] < m:
      l[2]+=1
      l[3]=l[2]-1
      while l[3] < m:
        l[3]+=1
        l[4]=l[3]-1
        while l[4] < m:
          l[4]+=1
          l[5]=l[4]-1
          while l[5] < m:
            l[5]+=1
            l[6]=l[5]-1
            while l[6] < m:
              l[6]+=1
              l[7]=l[6]-1
              while l[7] < m:
                l[7]+=1
                l[8]=l[7]-1
                while l[8] < m:
                  l[8]+=1
                  l[9]=l[8]-1
                  while l[9] < m:
                    l[9]+=1
                    ptmp = my_f(l, lq, q)
                    if ptmp > pmax:
                      pmax = ptmp

print(pmax)

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
ans = 0
zenbu = []
def tukuru(cur, last):
    if len(cur) == N:
        zenbu.append(cur)
        return
    for j in range(last, M+1):
        tukuru(cur+[j], j)
tukuru([], 1)
D = [0]*len(zenbu)
for i in range(Q):
    a, b, c, d = map(int, input().split())
    for i, p in enumerate(zenbu):
        if p[b-1] - p[a-1] == c:
            D[i] += d
print(max(D))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod = 10**9+7
import sys
from collections import Counter, defaultdict, deque
from itertools import product, permutations, combinations, combinations_with_replacement
from itertools import accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush
from math import ceil,floor
from copy import deepcopy
from heapq import heappop,heappush,heapify
import heapq


# l = ['a', 'a', 'a', 'a', 'b', 'c', 'c']
# c = Counter(l)

# d = defaultdict(int)

sys.setrecursionlimit(10 ** 6)

int1 = lambda x: int(x) - 1

# リストの要素を改行を挟んで表示する
p2D = lambda x: print(*x, sep="\n")
# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())

def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())

# 入力全てを整数に変換したものの配列を受け取る
# def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LI(): return list(map(lambda x:int(x), sys.stdin.readline().split()))
def HI(): return list(map(lambda x:int(x)*(-1), sys.stdin.readline().split()))



n,m,q = MI()
A =[]
B = []
C = []
D = []



for _ in range(q):
	a,b,c,d = MI()
	A.append(a)
	B.append(b)
	C.append(c)
	D.append(d)


ll = list(combinations_with_replacement(range(1,m+1), n))
	
ans = 0
for l in ll:
	tmp = 0
	for i in range(q):
		if l[(B[i]-1)]-l[(A[i]-1)]==C[i]:
			tmp+=D[i]

	ans = max(tmp,ans)
print(ans)

Submission status: Accepted

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

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

l = [i for i in range(1, m+1)]
ans = 0
for Alis in combinations_with_replacement(l, n):
    cnt = 0
    for i in range(q):
        if Alis[abcd[i][1] - 1] - Alis[abcd[i][0] - 1] == abcd[i][2]:
            cnt += abcd[i][3]
    ans = max(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
#import numpy as np
import math
#from fractions import gcd

def check_Q(current_list,Qset):

    sum_d = 0
    for i in range(len(Qset)):
        current_Qset = Qset[i]
        #print(current_Qset)
        #print(current_list)
        #print(sum_d)
        if (current_list[current_Qset[1]-1]-current_list[current_Qset[0]-1])==current_Qset[2]:
            sum_d = sum_d+current_Qset[3]

    return sum_d

def check_N(preget_list,zan_pre,M,nokori_N,Qset):

    if nokori_N==1:
        sum_list = []
        for i in range(zan_pre,M+1):
            current_list = preget_list+[i]
            sum_list.append(check_Q(current_list,Qset))

        return sum_list
    else:
        sum_list = []
        for i in range(zan_pre,M+1):
            current_list = preget_list+[i]
            sum_list = sum_list + check_N(current_list,i,M,nokori_N-1,Qset)

        return sum_list

def main():

    ##get int
    first_input = list(map(lambda x:int(x), input().split(" ")))
    #second_input = list(map(lambda x:int(x), input().split(" ")))

    ##get float
    #first_input = list(map(lambda x:float(x), input().split(" ")))
    #second_input = list(map(lambda x:float(x), input().split(" ")))

    ##get string
    #first_input = input().split(" ")

    N = first_input[0]
    M = first_input[1]
    Q = first_input[2]

    Qset = []
    for i in range(Q):
        secondkara_input = list(map(lambda x:int(x), input().split(" ")))
        Qset.append(secondkara_input)

    #print(check_N([],1,M,N,Qset))
    print(max(check_N([],1,M,N,Qset)))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n,m,q = map(int,input().split())
    Q = []
    for _ in range(q):
        a,b,c,d = map(int,input().split())
        Q.append([a,b,c,d])
    ans = 0
    for a in range(1,11):
        for b in range(a,11):
            for c in range(b,11):
                for d in range(c,11):
                    for e in range(d,11):
                        for f in range(e,11):
                            for g in range(f,11):
                                for h in range(g,11):
                                    for i in range(h,11):
                                        for j in range(i,11):
                                            l = [a,b,c,d,e,f,g,h,i,j]
                                            l = l[0:n]
                                            M = 0
                                            if max(l)>m:
                                                continue
                                            for q in Q:
                                                A,B,C,D = q[0],q[1],q[2],q[3]
                                                if l[B-1]-l[A-1] == C:
                                                    M += D
                                            if M>ans:
                                                ans = M
    print(ans)

    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

maxscore = 0



def solve():
    ans = [-1]*n
    ans[-1] = m
    rek(ans, m, 1)
    return

def rek(ans, m, rekdepth):
    global maxscore
    curr_ans = ans.copy()
    for i in range(1, m+1):
        curr_ans[-rekdepth-1] = i
        if rekdepth == n-1:
            score = get_score(curr_ans)
            maxscore = max(maxscore, score)
        else:
            rek(curr_ans.copy(), i, rekdepth + 1)


def get_score(arr):
    score = 0
    for (a, b, c, d) in abcd:
        if (arr[b-1] - arr[a-1] == c):
            score += d
    return score



# n = int(input())
n, m, q = [int(s) for s in input().split(" ")]
abcd = []
for i in range(q):
    abcd.append([int(s) for s in input().split(" ")])

solve()
print(maxscore)

Submission status: Accepted

Solution code:
N,M,Q=map(int,input().split())
query=[]
for i in range(Q):
    a,b,c,d=map(int,input().split())
    query.append([a,b,c,d])

ans=0
def dfs(list):
    global ans
    if len(list)==N:
        test=0
        for i in range(0,Q):
            a,b,c,d=query[i]
            if list[b-1]-list[a-1]==c:
                test+=d
        ans=max(test,ans)
        return 0
    if list:
        m=list[-1]
        for i in range(m,M+1):
            dfs(list+[i])
    else:
        for i in range(1,M+1):
            dfs([i])

dfs([])
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

ans = 0
for v in comb:
    tmp = 0
    for d in q_list:
        if v[d[1]-1] - v[d[0]-1] == d[2]: tmp += d[3]
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

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

num_all = [i+1 for i in range(M)]
#print(num_all)
Comb = list(itertools.combinations_with_replacement(num_all,N))

num_l = []         
for i in range(Q):
  a,b,c,d = map(int,input().split())
  num_l.append([a,b,c,d])
#print(num_l)  
  
#print(len(Comb))
d_sum_max = 0  
for A in Comb:
  d_sum = 0
  #print(A)
  #print()
  
  for x in num_l:
    a,b,c,d = x[0],x[1],x[2],x[3]
    #print(a,b,c,d)
    #print(A[b-1],A[a-1],':',A[b-1]-A[a-1],c)
    if(A[b-1]-A[a-1] == c):
      d_sum += d
      
  #print(A,d_sum)
  d_sum_max = max(d_sum_max,d_sum)

print(d_sum_max)

Submission status: Accepted

Solution code:
import itertools

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

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

ans = 0
for l in pat:
    cnt = 0
    for i in range(q):
        if l[abcd[i][1]-1] - l[abcd[i][0]-1] == abcd[i][2]:
            cnt += abcd[i][3]
    ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
import itertools

N,M,Q = map(int, input().split())
x = [list(map(int, input().split(" "))) for i in range(Q)]
list = list(itertools.combinations_with_replacement(range(1,M+1),N))


tmp = 0
mx = 0
for k in range(len(list)):
    for i in range(Q):
        a = x[i][0]
        b = x[i][1]
        c = x[i][2]
        d = x[i][3]
        if(list[k][b-1] - list[k][a-1]) == c:
            tmp += d
    mx = max(mx,tmp)
    tmp = 0

print(mx)

Submission status: Accepted

Solution code:
import itertools
N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]
A = [0]*N
ans = 0
bag = [i for i in range(1, M+1)]
for v in itertools.combinations_with_replacement(bag, N):
  an = 0
  for a, b, c, d in abcd:
    a -= 1
    b -= 1
    if v[b] - v[a] == c:
      an += d

  ans = max(ans, an)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

N,M,Q = map(int,input().split())
QUERY = [0]*Q
for i in range(Q):
    QUERY[i] = tuple(map(int,input().split()))

ans = 0
D = deque()
D.append((1,[1]))
dlen = 1
while dlen != 0:
    Alen,A = D.pop()
    dlen -= 1
    if Alen == N:
        e = 0
        for a,b,c,d in QUERY:
            a -= 1
            b -= 1
            if A[b] - A[a] == c:
                e += d
        ans = max(ans,e)
    else:
        for AA in range(A[-1],M+1):
            D.append((Alen+1,A+[AA]))
            dlen += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

seq=list(range(1,M+1))
ret=0

for A in combinations_with_replacement(seq,N):
    tmp=0
    for a,b,c,d in query:
        if A[b-1]-A[a-1]==c:
            tmp+=d
    
    ret=max(tmp,ret)

print(ret)

Submission status: Accepted

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

def score(l):
    ret = 0
    if len(l) == 0:
        for i in range(1, m+1):
            ret = max(ret, score([i]))
        return ret
    elif len(l) == n:
        for a,b,c,d in t:
            if l[b-1] -  l[a-1] == c:
                ret += d
        return ret
    else:
        for i in range(l[-1], m+1):
            ret = max(ret, score(l + [i]))
        return ret

print(score([]))

Submission status: Accepted

Solution code:
def main():
  n,m,q = map(int,input().split())
  
  a = [1]*n
    
  a_list = []
  while True:
    a_list.append([0, a[:]])
    end = True
    for i in range(n):
      index = n-1-i
      if a[index] < m:
        a[index] = a[index] + 1
        for j in range(i):
          a[index+1+j] = a[index]
        end = False
        break
    
    if end:
      break
  
  for _ in range(q):
    tmp = list(map(int, input().split()))
    for a in a_list:
      if a[1][tmp[1]-1] - a[1][tmp[0]-1] == tmp[2]:
        a[0] = a[0] + tmp[3]
  
  max = 0
  for a in a_list:
    if max < a[0]:
      max = a[0]
  
  return max

print(main())

Submission status: Accepted

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

from pprint import pprint
from collections import deque, defaultdict
import itertools
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline
INF = float("inf")

n, m, q = map(int, input().split())
queries = []
for i in range(q):
    line = list(map(int, input().split()))
    queries.append(line)

numbers = range(1, m + 1)

combs = itertools.combinations_with_replacement(numbers, n)
# print(list(combs))

res_max = 0
for A in combs:
    res = 0
    for a, b, c, d in queries:
        if A[b-1] - A[a-1] == c:
            res += d
    res_max = max(res_max, res)

print(res_max)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import combinations_with_replacement

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

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

result = 0
index = combinations_with_replacement(range(1, int(m) + 1), int(n))
for i in index:
    temp = 0
    for j in range(int(q)):
        if i[my_list[j][1] - 1] - i[my_list[j][0] - 1] == my_list[j][2]:
            temp += my_list[j][3]

    result = max(result, temp)

print(result)

Submission status: Accepted

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

def dsum(A):
    s = 0
    for r in rs:
        a, b, c, d = r
        if A[b-1] - A[a-1] == c:
            s += d
    return s

ma = 0
for a in combinations_with_replacement(range(1, m+1), n):
    ma = max(ma, dsum(a))
print(ma)

Submission status: Accepted

Solution code:
import copy


def repeat(pattern, before, n):
    for i in range(before, M + 1):
        new_pattern = copy.copy(pattern)
        new_pattern.append(i)
        if n != N - 1:
            repeat(new_pattern, i, n + 1)
        else:
            P.append(new_pattern)


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

combination = []
for _ in range(Q):
    combination.append([int(i) for i in input().split()])

P = []
for i in range(1, M + 1):
    repeat([i], i, 1)

a_max = 0
for p in P:
    a = 0
    for c in combination:
        if p[c[1] - 1] - p[c[0] - 1] == c[2]:
            a += c[3]
    if a_max <= a:
        a_max = a
print(a_max)

Submission status: Accepted

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

def f(nums):
  out=0
  for samp in abcd:
    if nums[samp[1]-1]-nums[samp[0]-1]==samp[2]:
      out+=samp[3]
  return out

def g(nums):
  if nums[-1]<M:
    nums[-1]+=1
    return nums, False
  
  i=N-1
  while i>=0 and nums[i]==M:
    i-=1
  if i<0:
    return None, True
  
  nums=nums[:i]+[nums[i]+1 for _ in range(N-i)]
  return nums, False

nums=[1]*N
fi=False
ans=0

while fi==False:
  p=f(nums)
  if ans<p:
    ans=p
  nums, fi=g(nums)
  
print(ans)

Submission status: Accepted

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

nums = [i for i in range(1, m + 1)]
ans = 0
for nums in itertools.combinations_with_replacement(nums, r=n):
	tmp = 0
	for query in queries:
		if nums[query[1] - 1] - nums[query[0] - 1] == query[2]:
			tmp += query[3]
	ans = max(ans, tmp)
print(ans)

Submission status: Accepted

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


def solve(N: int, M: int, Q: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
    A = [0]
    def rb(i=0):
        if i < N:
            ans = 0
            for j in range(1, M + 1):
                if j >= A[-1]:
                    A.append(j)
                    ans = max(ans, rb(i + 1))
                    A.pop()
            return ans
        else:
            return sum(d[j] for j in range(Q) if A[b[j]] - A[a[j]] == c[j])
    print(rb())


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    a = [int()] * (Q)  # type: "List[int]"
    b = [int()] * (Q)  # type: "List[int]"
    c = [int()] * (Q)  # type: "List[int]"
    d = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
        d[i] = int(next(tokens))
    solve(N, M, Q, a, b, c, d)

if __name__ == '__main__':
    main()

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 _ in range(q)]
    ans=0
    L=list(range(1,m+1))
    for Q in combinations_with_replacement(L,n):
        Q=list(sorted(Q))
        tmp=0
        for a,b,c,d in ABCD:
            if Q[b-1]-Q[a-1]==c:
                tmp+=d
        ans=max(ans,tmp)
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def main():
	n,m,q = map(int,input().split())
	qu = [list(map(int,input().split())) for x in range(q)]
	ans = 0
	import itertools

	ans_list = set()
	for i in itertools.combinations_with_replacement(list(range(1,m+1)),n):
		for qul in range(q):
			if i[ qu[qul][1]-1 ] - i[ qu[qul][0]-1 ] == qu[qul][2]:
				ans += qu[qul][3]
		ans_list.add(ans)
		ans = 0
	print(max(ans_list))

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import itertools

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

for A_ in itertools.combinations_with_replacement([i for i in range(1, M+1)], N):
    A = list(A_)
    tmp_ans = 0
    for i in range(Q):
        if A[list_q[i][1]-1] - A[list_q[i][0]-1] == list_q[i][2]:
            tmp_ans += list_q[i][3]
    if ans < tmp_ans:
        ans = tmp_ans

print(ans)

Submission status: Accepted

Solution code:
import itertools
N, M, Q = map(int, input().split())
tapple = []
d_sum_max = 0
for i in range(Q):
    tapple.append([int(n) for n in input().split()])
A = list(itertools.combinations_with_replacement(range(1, M+1), N))
for j in range(len(A)):
    d_sum = 0
    for i in range(Q):
        if A[j][tapple[i][1]-1] - A[j][tapple[i][0]-1] == tapple[i][2]:
            d_sum += tapple[i][3] 
    if d_sum_max < d_sum:
        d_sum_max = d_sum
print(d_sum_max)

Submission status: Accepted

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

a_base = [i for i in range(1,m+1)]
a_ls = []
for A in itertools.combinations_with_replacement(a_base, n):
    istarget = True
    for i in range(n-1):
        if A[i] > A[i+1]:
            istarget = False
    if istarget:
        a_ls.append(list(A))
ans = 0
for A in a_ls:
    value_of_A = 0
    for a,b,c,d in num_ls:
        if A[b-1] - A[a-1] == c:
            value_of_A += d
    ans = max(ans, value_of_A)
print(ans)

Submission status: Accepted

Solution code:
from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
import itertools
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

N,M,Q = FLI()
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] = FLI()
H = []
for j in range(1, M+1):
    H.append(j)
L = list(itertools.combinations_with_replacement(H,N))
max = 0
for l in L:
  sum = 0
  for q in range(Q):
    if l[b[q]-1] - l[a[q]-1] == c[q]:
        sum += d[q]
  if max < sum:
      max = sum

print(max)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
N, M, Q = [int(n) for n in input().split()]
X = [[int(n) for n in input().split()] for _ in range(Q)]
ans = []
for A in combinations_with_replacement(range(1, M+1), N):
    t = 0
    for x in X:
        if A[x[1]-1]-A[x[0]-1] == x[2]:
            t += x[3]
    ans.append(t)
print(max(ans))

Submission status: Accepted

Solution code:
import itertools
n,m,q=map(int,input().split())
abcd=[list(map(int,input().split())) for i in range(q)]
A=[i for i in range(1,m+1)]
arr=list(itertools.combinations_with_replacement(A, n))

ans=0
for i in arr:
  p=0
  for j in range(q):
    a,b,c,d=abcd[j][0],abcd[j][1],abcd[j][2],abcd[j][3]
    if i[b-1]-i[a-1]==c:
      p+=d
  ans=max(ans,p)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement


def sol(A):
    tmp_ans = 0
    for row in B:
        a, b, c, d = row
        a -= 1
        b -= 1
        if A[b] == A[a] + c:
            tmp_ans += d
    return tmp_ans


if __name__ == '__main__':
    N, M, Q = map(int, input().split())
    A = [1 for _ in range(N)]
    used = [False for _ in range(N)]

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

    cnt = 0
    ans = 0
    for A in combinations_with_replacement([i for i in range(1, M + 1)], N):
        ans = max(ans, sol(A))

    print(ans)

Submission status: Accepted

Solution code:
import itertools

def main(N, M, Q, input):
    '''
    配列Aを求める→得点をreturn
    A: 長さN, 最大値Mの配列
    '''

    max_score = 0
    for i in [sorted(i) for i in list(itertools.combinations_with_replacement([i + 1 for i in range(M)], N))]:
        score = 0
        for j in range(Q):
            if i[input[j][1] - 1] - i[input[j][0] - 1] == input[j][2]: #pythonでは一つindexがずれるため．
                score += input[j][3]
        max_score = max(max_score, score)
    print(max_score)



if __name__ == '__main__':
    N, M, Q = list(map(int, input().split()))
    input = [list(map(int, input().split())) for i in range(Q)]
    main(N, M, Q, input)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools

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

mx = 0
for case in itertools.combinations_with_replacement(range(1, m+1), n):
    total = 0
    for i in range(q):
        if case[l[i][1]-1] - case[l[i][0]-1] == l[i][2]:
            total += l[i][3]
    mx = max(mx, total)
print(mx)

Submission status: Accepted

Solution code:
import itertools
N, M, Q = map(int, input().split())
S = [list(map(int, input().split())) for i in range(Q)]
sum_list = []
A_list = list(itertools.combinations_with_replacement(range(1, M+1), N))
for k in range(len(A_list)):
    A = A_list[k]
    sum = 0
    for i in range(Q):
        #S = list(map(int, input().split()))
        if A[S[i][1] - 1] - A[S[i][0] - 1] == S[i][2]:
        #if A[S[1] - 1] - A[S[0] - 1] == S[2]:
            sum += S[i][3]
    sum_list.append(sum)
print(max(sum_list))

Submission status: Accepted

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

for v in itertools.combinations_with_replacement(l,n):
	for i in range(q):
		if v[b[i]-1] - v[a[i]-1] == c[i]:
			sum += d[i]
	if max < sum:
		max = sum
	sum = 0
print(max)

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)
  b.append(B)
  c.append(C)
  d.append(D)
ans=0
M=[0,0,0,0,0,0,0,0,0,0,0]
for i in range(n):
  M[i]=1
cursor=n
breakflag=0
while True:
  ev=0
  for i in range(q):
    if M[b[i]-1]-M[a[i]-1]==c[i]:
      ev+=d[i]
  if ev>ans:
    ans=ev
  while True:
    if M[cursor-1]<m:
      M[cursor-1]+=1
      for i in range(cursor,n):
        M[i]=M[cursor-1]
      cursor=n
      break
    cursor-=1
    if cursor==0:
      breakflag=1
      break
  if breakflag==1:
    break
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

for i in num_li:
    temp = 0
    for j in li:
        a,b,c,d = j
        if i[b-1] - i[a-1] == c:
            temp += d
    ans = max(ans,temp)
print(ans)

Submission status: Accepted

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

vs = [j for j in range(1, M + 1)]

temp = []
for v in vs:
    temp.append([v])

use = []
while True:
    hoge = []
    for i in temp:
        index = vs.index(i[-1])
        for v in vs[index:]:
            hoge.append(i + [v])
    temp = hoge
    if len(hoge[0]) == N:
        use = hoge
        break

ans = 0
for u in use:
    t = 0
    for v in a:
        if u[v[1] -1] - u[v[0] -1] == v[2]:
            t += v[3]
    ans = max(ans, t)

print(ans)

Submission status: Accepted

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

ABCD.sort(key=lambda x:x[3],reverse=True)

from itertools import combinations_with_replacement,product
a = []
for i in range(M):
    a.append(i+1)
L = list(combinations_with_replacement(a,N))

out = 0
for X in L:
    cand = 0
    for i in range(Q):
        A = ABCD[i][0]
        B = ABCD[i][1]
        C = ABCD[i][2]
        D = ABCD[i][3]
        if X[B-1]-X[A-1]==C:
            cand += D
    if cand>out:
        out = cand
print(out)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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


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

Submission status: Accepted

Solution code:
[n, m, q] = [int(x) for x in input().split(' ')]

a = []
b = []
c = []
d = []

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

x = [1] * n

def next(x):
  for i in range(n-1, -1, -1):
    if x[i] != m:
      x[i] += 1
      for j in range(i, n):
        x[j] = x[i]
      return True
  else:
    return False

def score(x):
  s = 0
  for i in range(q):
    if x[b[i]] - x[a[i]] == c[i]:
      s += d[i]
  return s

ans = score(x)
while next(x):
  ans = max(ans, score(x))

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

ALIST = list(itertools.combinations_with_replacement([i for i in range(1, M+1)], N))

total = 0

for A in ALIST:
  tokuten = 0
  for a, b, c, d in ABCD:
    diff = A[b-1] - A[a-1]
    if diff == c:
      tokuten += d
  total = max(total, tokuten)
print(total)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as combi

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

com = list(combi(list(range(1, m+1)), n))

total = []

for lis in com:
    tot = 0
    for cond in c:
        idx1 = cond[0]-1
        idx2 = cond[1]-1
        diff = cond[2]
        if lis[idx2] - lis[idx1] == diff:
            tot += cond[3]
    total.append(tot)

print(max(total))

Submission status: Accepted

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

ls = deque([[1]])
while True:
  v = ls.popleft()
  if len(v) == N+1:
    ls.append(v)
    break
  matubi = int(v[-1])
  for i in range(matubi,M+1):
    ls.append(v+[i])

def check(s):
  karid = 0
  for i in range(Q):
    a,b,c,d = l[i]
    if int(s[b]) - int(s[a]) == c:
      karid += d
  return karid

ans = 0
for i in range(len(ls)):
  s = ls[i]
  ans = max(check(s),ans)
print(ans)