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())
table = [list(map(int, input().split())) for i in range(Q)]

best = 0


def cal_score(A):
    global table
    score = 0
    for i in table:
        if (A[i[1]-1] - A[i[0]-1]) == i[2]:
            score += i[3]
    return score


def next_number(A):
    global best
    global N
    global M
    if len(A) == N:
        return cal_score(A)
    if len(A) == 0:
        min_num = 1
    else:
        min_num = A[-1]
    candidate = list(range(min_num, M+1))
    for i in candidate:
        A.append(i)
        score = next_number(A)
        if score > best:
            best = score
        A.pop(-1)
    return best


A = []
print(next_number(A))

Submission status: Accepted

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

l = []
for i in range(m):
    l.append(i)
maximum = 0
for a in itertools.combinations_with_replacement(l, n):
    sum = 0
    for i in range(q):
        if a[abcd[i][1]] - a[abcd[i][0]] == abcd[i][2]:
            sum += abcd[i][3]
    maximum = max(maximum,sum)
print(maximum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import *
N,M,Q=[int(s) for s in input().split()]
Qls=[[int(s) for s in input().split()] for _ in range(Q)]
for i in range(Q):
  Qls[i][0]-=1
  Qls[i][1]-=1
iterable=range(1, M+1)
checkls=list(combinations_with_replacement(iterable, N))
ans=set()
for ls in checkls:
  score=0
  for a,b,c,d in Qls:
    if ls[b]-ls[a]==c:
      score+=d
  ans.add(score)
print(max(ans))

Submission status: Accepted

Solution code:
import itertools
n, m, q = map(int,input().split())
A = itertools.combinations_with_replacement(range(1,m+1),n)
cond = [list(map(int,input().split())) for i in range(q)]
ma = 0
for a in A:
    p = 0
    for c in cond:
        if a[c[1]-1]-a[c[0]-1] == c[2]:
            p += c[3]
    if ma < p:
        ma = p

print(ma)

Submission status: Accepted

Solution code:
from itertools import combinations

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

max_score = 0
for t in combinations(list(range(m-1+n)), n):
    cur = 1
    A = []
    for i in range(m-1+n):
        if i in t:
            A.append(cur)
        else:
            cur += 1

    score = 0
    for k in range(q):
        if A[b[k]] - A[a[k]] == c[k]:
            score += d[k]
    max_score = max(max_score, score)

print(max_score)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

max_score = 0
for pattern in combinations_with_replacement(range(1, M + 1), N):
    score = 0
    for row in input_lst:
        a, b, c, d = row
        if pattern[b - 1] - pattern[a - 1] == c:
            score += d
    if score > max_score:
        max_score = score
print(max_score)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement


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

ans = 0
for A in combinations_with_replacement(range(1, m + 1), n):
    temp = 0
    for a, b, c, d in QUERY:
        a -= 1; b -= 1
        if A[b] - A[a] == c:
            temp += d
    ans = max(ans, temp)

print(ans)

Submission status: Accepted

Solution code:
import itertools
#1~Mと仕切りN枚を適宜並べ、「左にあるかずの個数」を考える。
#1~N+Mの中からN個選ぶ
N,M,Q = [int(hoge) for hoge in input().split()]
L = list(itertools.combinations(range(1,M+N),N))
abcd = [[int(hoge) for hoge in input().split()] for q in range(Q)]

curmax = 0
for l in L:
    suretu = []
    score = 0
    for n,k in enumerate(l):#数列を実際に生成
        #(1,2,5,6,7,9)とか出てくるので…
        suretu.append(k-n)
    for a,b,c,d in abcd:
        if suretu[b-1] - suretu[a-1] == c:
            score += d
    curmax = max(curmax,score)
print(curmax)

Submission status: Accepted

Solution code:
def saiki(N,M):
  #print(N,M)
  if N == 1:
    return [[i]for i in range(1,M+1)]
  else:
    buf = saiki(N-1, M)
    res = []
    for val in buf:
      res += [val + [i] for i in range(val[-1],M+1)]
    return res
      

N, M, Q = map(int, input().split())
cases = saiki(N,M)
highest = 0
a = [0 for i in range(Q)]
b = list(a)
c = list(a)
d = list(a)

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

#print(a,b,c,d)
for case in cases:
  summ = 0
  for i in range(Q):
    if case[b[i]-1]-case[a[i]-1]==c[i]:
      summ += d[i]
  highest = max(highest, summ)
print(highest)

Submission status: Accepted

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
MOD = 10**9+7


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

p = []
def dfs(dmax,now):
    if len(now) == n:
        p.append(now)
        return
    for i in range(dmax,m+1):
        dfs(i,now+[i])
dfs(1,[])
Ans = 0
for i in range(len(p)):
    ans = 0
    for j in range(len(Query)):
        if p[i][Query[j][1]] - p[i][Query[j][0]] == Query[j][2]:
            ans += Query[j][3]
    Ans = max(Ans,ans) 
print(Ans)

Submission status: Accepted

Solution code:
# C
# Many Requirements
import itertools

N, M, Q = map(int, input().split())
tmp_ = list(range(1,M+1))
A_tensor = itertools.combinations_with_replacement(tmp_,N)
S_list = []

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

ans = 0

for _list in A_tensor:
    tmp_score = 0
    for j in range(Q):
        if _list[S_list[j][1]-1] - _list[S_list[j][0]-1] == S_list[j][2]:
            tmp_score += S_list[j][3]
    if tmp_score > ans:
        ans = tmp_score

print(ans)

Submission status: Accepted

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #ここにコード
    #input
    N, M, Q = map(int, input().split())

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

    #output
    import itertools
    #A[b-1] = A[a-1] + c
    L = [i+1 for i in range(M)]

    L = itertools.combinations_with_replacement(L, N)

    answer = 0
    for l in L:
        temp_answer = 0
        for i in range(Q):
            a = e[i][0]
            b = e[i][1]
            c = e[i][2]
            d = e[i][3]
            if l[b-1] - l[a-1] == c:
                temp_answer += d
                answer = max(answer, temp_answer)

    print(answer)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools

def checker(num):
    if A[rules[num][1] - 1] - A[rules[num][0] - 1] == rules[num][2]:
        return rules[num][3]
    else:
        return 0

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

temp = []
for i in range(M):
    temp.append(i + 1)
    
test = list(itertools.combinations_with_replacement(temp, N))

for _ in range(Q):
    rules.append(list(map(int,input().split())))
    

output = 0

for i in range(len(test)):
    A = test[i]
    
    score = 0
    for i in range(Q):
        score += checker(i)
    output = max(output,score)
    
print(output)

Submission status: Accepted

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

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

def dfs(seq):
    if len(seq) == n:
        yield seq
        return

    if len(seq) == 0:
        _max = 1
    else:
        _max = seq[-1]

    for i in range(_max, m+1):
        new_seq = seq.copy()
        new_seq.append(i)
        yield from dfs(new_seq)

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

print(ans)

Submission status: Accepted

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

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

P = []
def dfs(dmax, now):
    if len(now) == N:
        P.append(now)
        return
    for n in range(dmax, M+1):
        dfs(n, now+[n])
dfs(1, [])
ans = 0
for A in P:
    score = 0
    for a, b, c, d in ABCD:
        if A[b-1] - A[a-1] == c:
            score += d
    ans = max(ans, score)

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

N, M, Q = (int(_) for _ in input().split())

abcd = []
for q in range(Q):
    abcd.append([int(_) for _ in input().split()])
    
ret = 0
for i in combinations(list(range(N + M - 1)), N):
    # A = [i[0] + 1]
    # for ii in range(len(i) - 1):
    #     A.append(i[ii + 1] - i[ii] + A[ii] - 1)
    # print(A)
    subret = 0
    for a, b, c, d in abcd:
        if i[b - 1] - i[a - 1] - (b - a) == c:
            subret += d
    ret = max(ret, subret)
print(ret)

Submission status: Accepted

Solution code:
def dfs(nums, length, min_lim):
    ans = 0
    if length == n:
        score_ret = 0
        for a,b,c,d in req:
            if nums[b] - nums[a] == c:
                score_ret += d
        return score_ret
    else:
        for nu in range(min_lim, m + 1):
            new_nums = nums + [nu]
            score = dfs(new_nums, length + 1, nu)
            ans = max(ans, score)
    return ans

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

req = [list(map(int, input().split())) for _ in range(q)]
ans = dfs([-1], 0, 1)
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)]

AA=itertools.combinations_with_replacement(range(1,m+1),n)		#結果はsortされる

res=0

for A in AA:
	cnt=0
	for a,b,c,d in abcd:
		if A[b-1]-A[a-1]==c:
			cnt+=d
	res=max(res,cnt)
	
print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def solve(cur_index):
    global ret
    if cur_index == N:
        tmp_sum = 0
        for i in range(Q):
            if A[b[i]] - A[a[i]] == c[i]:
                tmp_sum += d[i]
        ret = max(ret, tmp_sum)
        return
    for i in range(min(A[cur_index], M), M + 1):
        A[cur_index + 1] = i
        solve(cur_index + 1)


if __name__ == '__main__':
    N, M, Q = map(int, input().split())
    a = [0 for _ in range(Q)]
    b = [0 for _ in range(Q)]
    c = [0 for _ in range(Q)]
    d = [0 for _ in range(Q)]
    for i in range(Q):
         a[i], b[i], c[i], d[i] = map(int, input().split())
    ret = 0
    A = [1 for _ in range(N + 1)]
    solve(0)
    print(ret)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# C - Many Requirements
from itertools import combinations_with_replacement


def main():
    N, M, Q, *ABCD = map(int, open(0).read().split())
    conditions = tuple(zip(*[iter(ABCD)] * 4))
    ans = max(
        sum(d for a, b, c, d in conditions if comb[b - 1] - comb[a - 1] == c)
        for comb in combinations_with_replacement(range(1, M + 1), N)
    )
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import combinations_with_replacement

input = sys.stdin.buffer.readline


def main():
    n_ints, max_int, n_queries = map(int, input().split())

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

    possible_sequences = combinations_with_replacement(range(1, max_int+1), n_ints)

    max_score = 0
    for sequence in possible_sequences:
        score = 0

        for i, q in enumerate(queries):
            a, b, c, d = q
            if sequence[b-1] - sequence[a-1] == c:
                score += d

        max_score = max(max_score, score)

    print(max_score)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement


def main():
    n_ints, max_int, n_queries = map(int, input().split())

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

    possible_sequences = combinations_with_replacement(range(1, max_int+1), n_ints)

    max_score = 0
    for sequence in possible_sequences:
        score = 0

        for i, q in enumerate(queries):
            a, b, c, d = q
            if sequence[b-1] - sequence[a-1] == c:
                score += d

        max_score = max(max_score, score)

    print(max_score)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy, copy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M, Q = MAP()
abcd = [LIST() for _ in range(Q)]
ans = 0

def DFS(l):
 	global ans 
 	#print(l)
 	if len(l) == N:
 		tmp = 0
 		for a, b, c, d in abcd:
 			a -= 1
 			b -= 1
 			if l[b] - l[a] == c:
 				tmp += d
 		ans = max(ans, tmp)
 	else:
 		for i in range(l[-1], M+1):
 			DFS(l+(i,))

for i in range(1, M+1):
 	DFS((i,))

print(ans)

Submission status: Accepted

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

def dfs(A:list):
    global n, m, q, ans
    if (len(A) == n+1):
        now = 0
        for i in range(q):
            if (A[abcd[i][1]] - A[abcd[i][0]] == abcd[i][2]):
                now += abcd[i][3]
        ans = max(now, ans)
        return
    
    for v in range(A[-1],m+1):
        A.append(v)
        dfs(A)
        A[-1] += 1
        A.pop()

        
dfs([1])

print(ans)

Submission status: Accepted

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

def calc_score(A):
   score = 0
   for a, b, c, d in lists:
       if A[b - 1] - A[a - 1] == c:
           score += d
   return score

def dfs(A):
   global ans
   if len(A) == N:
       score = calc_score(A)
       ans = max(score, ans)
       return
   for n in range(A[-1], M + 1):
       dfs(A + [n])

dfs([1])
print(ans)

Submission status: Accepted

Solution code:
import itertools

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


A = list(range(1,M+1))
MAX = 0
for L in itertools.combinations_with_replacement(A,N):
    SUM = 0
    for a,b,c,d in ABCD:
        if L[b] - L[a] == c:
            SUM += d

    MAX = max(SUM,MAX)
print(MAX)

Submission status: Accepted

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

A=[1 for _ in range(N)]
ans=0

for i in range(10**9):
    temp=0
    for j in range(Q):
        if A[a[j][1]-1]-A[a[j][0]-1]==a[j][2]:
            temp+=a[j][3]
    ans=max(ans,temp)
    A[-1]+=1
    if A[-1]>M:
        k=1
        while max(A)>M and k<N:
            A[N-k-1]+=1
            A[N-k]=A[N-k-1]
            k+=1
            for l in range(1,k):
                A[N-l]=A[N-k]
    if min(A)>M:
        break
print(ans)

Submission status: Accepted

Solution code:
def dfs(A):
    if len(A)==N:
        temp=0
        for j in range(Q):
            if A[a[j][1]-1]-A[a[j][0]-1]==a[j][2]:
                temp+=a[j][3]
        ans.append(temp)
        return
    else:
        if len(A)>0:
            m=A[-1]
        else:
            m=1
        for i in range(m,M+1):
            A.append(i)
            dfs(A)
            A.pop()
        
N,M,Q=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(Q)]
ans=[]
dfs([])
print(max(ans))

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 += [a_-1]
    b += [b_-1]
    c += [c_]
    d += [d_]

def score(A):
    ret = 0
    for i in range(Q):
        if A[b[i]] - A[a[i]] == c[i]:
            ret += d[i]
    return ret


def dfs(li):
    if len(li) == N:
        global ans
        ans = max(ans, score(li))
    else:
        if li == []:
            st = 1
        else:
            st = li[-1]
        for i in range(st, M+1):
            li.append(i)
            dfs(li)
            li.pop()

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

Submission status: Accepted

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

abcd = [list(map(int, input().split())) for _ in range(q)]
from itertools import combinations_with_replacement as cwr
AList = list(cwr(range(1, m+1), n))


maxPoint = 0
for A in AList:
  point = 0
  for abc in abcd:
    a = abc[0]
    b = abc[1]
    c = abc[2]
    d = abc[3]
    if A[b-1] - A[a-1] == c:
      point += d
  if point > maxPoint:
    maxPoint = point
print(maxPoint)

Submission status: Accepted

Solution code:
from sys import stdin
# import sys
import math


def cmd(n, r):
    return math.factorial(n) // (math.factorial(n - r)*math.factorial(r))


def bts(cnt, A):
    if cnt == N:
        # K += 1
        # print(A)
        global ans
        temp = 0
        for i in range(Q):
            if A[b[i]-1]-A[a[i]-1] == c[i]:
                temp += d[i]
        if temp > ans:
            ans = temp
        # print(ans)
        return
    if len(A) == 0:
        x = 1
    else:
        x = A[-1]
    for i in range(x, M+1):
        # print(i)
        A.append(i)
        bts(cnt+1, A)
        for i in range(cnt, len(A)):
            A.pop()


N, M, Q = [int(x) for x in stdin.readline().rstrip().split()]
# N = [int(x) for x in stdin.readline().rstrip().split()]
# N = int(input())
# U = input().split()
# A, B = [str(x) for x in stdin.readline().rstrip().split()]
global a, b, c, d, ans
ans = 0
a = []
b = []
c = []
d = []
for i in range(Q):
    a1, b1, c1, d1 = [int(x) for x in stdin.readline().rstrip().split()]
    a.append(a1)
    b.append(b1)
    c.append(c1)
    d.append(d1)
global A
A = []
global K
K = 0
cnt = 0
# print(A[K][-1])
bts(cnt, A)
# print(A)
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

max_score = 0
for aa in Alist:
    a = list(aa)
    score = 0
    for l in range(q):
        if a[p[l][1]-1]-a[p[l][0]-1] == p[l][2]:
            score += p[l][3]
    max_score = max(max_score,score)
print(max_score)

Submission status: Accepted

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

ans=0

def henkan(A,ABCD):
    cnt=0
    for i in range(len(ABCD)):
        a=ABCD[i][0]
        b=ABCD[i][1]
        c=ABCD[i][2]
        d=ABCD[i][3]
        if A[b-1]-A[a-1]==c:
            cnt+=int(d)
    return cnt

A=[0]*N
for q in range(1,M+1):
    A[0]=q
    for w in range(A[0],M+1):
        A[1]=w
        if N==2:
            if ans<=henkan(A,ABCD):
                ans=henkan(A,ABCD)
            else:
                pass
        else:
            for e in range(A[1],M+1):
                A[2]=e
                if N==3:
                    if ans<=henkan(A,ABCD):
                        ans=henkan(A,ABCD)
                    else:
                        pass
                else:
                    for r in range(A[2],M+1):
                        A[3]=r
                        if N==4:
                            if ans<=henkan(A,ABCD):
                                ans=henkan(A,ABCD)
                            else:
                                pass
                        else:
                            for t in range(A[3],M+1):
                                A[4]=t
                                if N==5:
                                    if ans<=henkan(A,ABCD):
                                        ans=henkan(A,ABCD)
                                    else:
                                        pass
                                else:
                                    for y in range(A[4],M+1):
                                        A[5]=y
                                        if N==6:
                                            if ans<=henkan(A,ABCD):
                                                ans=henkan(A,ABCD)
                                            else:
                                                pass
                                        else:
                                            for u in range(A[5],M+1):
                                                A[6]=u
                                                if N==7:
                                                    if ans<=henkan(A,ABCD):
                                                        ans=henkan(A,ABCD)
                                                    else:
                                                        pass
                                                else:
                                                    for i in range(A[6],M+1):
                                                        A[7]=i
                                                        if N==8:
                                                            if ans<=henkan(A,ABCD):
                                                                ans=henkan(A,ABCD)
                                                            else:
                                                                pass
                                                        else:
                                                            for o in range(A[7],M+1):
                                                                A[8]=o
                                                                if N==9:
                                                                    if ans<=henkan(A,ABCD):
                                                                        ans=henkan(A,ABCD)
                                                                    else:
                                                                        pass
                                                                else:
                                                                    for p in range(A[8],M+1):
                                                                        A[9]=p
                                                                        if N==10:
                                                                            if ans<=henkan(A,ABCD):
                                                                                ans=henkan(A,ABCD)
                                                                            else:
                                                                                pass
print(ans)

Submission status: Accepted

Solution code:
from collections import *

def dfs(now):
    global ans
    
    if len(now)==N:
        ans_cand = 0
        
        for a, b, c, d in abcd:
            if now[b-1]-now[a-1]==c:
                ans_cand += d
        
        ans = max(ans, ans_cand)
        return
    
    last = now[-1]
    
    for i in range(last, M+1):
        now.append(i)
        dfs(now)
        now.pop()

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

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

print(ans)

Submission status: Accepted

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

abcd=list()
for i in range(q):
    abcd.append([int(e) for e in input().split()])

a=[]
b=[]
def combi(n,m,r=1): #nはN数、mは最大数,rは際少数
    if len(a) == n:
        b.append([0 for _ in range(n)])
        for i,v in enumerate(a):
            b[-1][i] += v
    else:
        for i in range(r,m+1):
            a.append(i)
            combi(n,m,i)
            a.pop()
    return(b)



all = combi(n,m)

count=list()
num=0
for i in all:
    for j in abcd:
        if i[j[1]-1]-i[j[0]-1] == j[2]:
            num += j[3]
        else:
            pass
    count.append(num)
    num=0

print(max(count))

Submission status: Accepted

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

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

def dfs(seq):
    if len(seq) == n:
        yield seq
        return

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations, product
n, m, q = [int(i) for i in sys.stdin.readline().split()]
ls = []
for i in range(q):
    a, b, c, d = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    ls.append([a, b, c, d])

def check_ls(ls, A):
    cnt = 0
    for a, b, c, d in ls:
        if A[b] - A[a] == c:
            cnt += d
    return cnt

_best = 0
res = []

def dfs(last, cur):
    flg = len(cur) < n - 1
    for i in range(last, 1+m):
        if flg:
            dfs(i, cur + [i])
        else:
            res.append(cur + [i])

dfs(1, [])
for i in res:
    i = [int(j) for j in i]
    _best = max(_best, check_ls(ls, i))
print(_best)

Submission status: Accepted

Solution code:
import numpy as np

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


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() )
#    print( a[ i ], b[ i ], c[ i ], d[ i ] )


def loopA( ai ):
    global ans

    if ai == n:
#        print( A )
        sumA = int( 0 )
        for j in range( q ):
            if A[ b[j]-1 ] - A[ a[j]-1 ] == c[j]:
                sumA += d[ j ]
        ans = max( ans, sumA )

    elif ai <= n-1:
        for i in range( 1 if ai == 0 else A[ ai-1 ], m+1 ):
            A[ ai ] = i
            loopA( ai+1 )



A = [ 1 ] * n
ans = int( 0 )

loopA( 0 )
print( ans )

Submission status: Accepted

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

import itertools as it
abcd=list()
for i in range(q):
    abcd.append([int(e) for e in input().split()])


all = it.combinations_with_replacement(range(1,m+1),n)

count=list()
num=0
for i in all:
    for j in abcd:
        if i[j[1]-1]-i[j[0]-1] == j[2]:
            num += j[3]
        else:
            pass
    count.append(num)
    num=0

print(max(count))

Submission status: Accepted

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

for i in range(Q):
    a[i],b[i],c[i],d[i]=map(int,input().split())
    a[i]-=1
    b[i]-=1    #Aのa[i],b[i]番目を指定したいから-1する。

def score(A):
    一つ一つの点数=0
    for ai,bi,ci,di in zip(a,b,c,d):
        if A[bi]-A[ai]==ci:
            一つ一つの点数+=di
    return 一つ一つの点数

def dfs(A):
    if len(A)==N:
        return score(A)
    暫定の点数=0
    数列=A[-1] if len(A)>0 else 0
    for v in range(数列,M):
        A.append(v)
        暫定の点数=max(暫定の点数,dfs(A))    #再帰関数を呼び出しながら暫定1位の点数を更新。
        A.pop()
    return 暫定の点数

print(dfs([]))

Submission status: Accepted

Solution code:


MAX = 0
M = 0
N = 0
def dfs(A:list,ABCD:list):
    global MAX,N,M
    if(len(A) == N):
        total = 0
        for a,b,c,d in ABCD:
            if(A[b - 1] - A[a - 1] == c):
                total += d
        MAX = max(MAX,total)
        return
    pre = A[-1] if(len(A) > 0) else 1
    for v in range(pre,M+1):
        A.append(v)
        dfs(A,ABCD)
        A.pop()

def main():
    global N,M
    N,M,Q = map(int,input().split())
    lis = []
    for _ in range(Q):
        lis.append(list(map(int,input().split())))
    dfs([],lis)
    print(MAX)

if __name__ == "__main__":
    main()