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 itertools
n, m, q = [int(i) for i in input().split(" ")]
A = []
for i in range(q):
    A.append([int(i) for i in input().split(" ")])
given = [i for i in range(1, m + 1)]
ans = itertools.combinations_with_replacement(given, n)
answer = 0
for solve in ans:
    now = 0
    for i in range(q):
        if (solve[A[i][1] - 1] - solve[A[i][0] - 1]) == A[i][2]:
            now += A[i][3]
    if (now > answer):
        answer = 0 + now
print(answer)

Submission status: Accepted

Solution code:
from itertools import combinations
import sys
input = lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(20000000)

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

# def check(Q):
#     A = [1] + [-1 for _ in range(n-1)]
#     score = 0
#     for a, b, c, d in Q:
#         if A[a] == -1 and A[b] == -1:
#             tmp_b = min(A[b:])
#             if tmp_b == -1 or tmp_b >= max(A[:a]) + c:
#                 A[a] = max(A[:a])
#                 A[b] = A[a] + c
#                 score += d
#         elif A[a] == -1 and A[b] != -1:
#             if max(A[:a]) <= A[b] - c <= max(A[:a]):
#                 A[a] = A[b] - c
#                 score += d
#         elif A[a] != -1 and A[b] == -1:
#             if min(A[:b]) <= A[a] + c <= max(A[b:]):
#                 A[b] = A[a] + c
#                 score += d
#         else:
#             if A[b] - A[a] == c:
#                 score += d
#         print(A)
#     return score

def dfs(A, depth, max_a):
    if depth == n:
        score = 0
        for a, b, c, d in abcd:
            if A[b] - A[a] == c:
                score += d
        return score
    ans = 0
    for i in range(max_a, m+1):
        ans = max(ans, dfs(A + [i], depth+1, i))
    return ans

ans = dfs([1], 1, 1)
print(ans)

Submission status: Accepted

Solution code:
import itertools

def main():
  n, m, q = map(int,input().split())
  ans_li = []
  li = []
  for i in range(q):
    a, b, c, d = map(int,input().split())
    li.append([a,b,c,d])
  
  for i in itertools.combinations_with_replacement(range(1,m+1), n):
    ans = 0
    for j in li:
      if i[j[1]-1] - i[j[0]-1] == j[2]:
        ans += j[3]
    ans_li.append(ans)
  print(max(ans_li))

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N,M,Q = map(int, input().split())

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

def next(A):
  index = -1
  while True:
    if A[index]<M:
      return A[:index]+[A[index]+1 for i in range(-index)]
    else:
      index -= 1
      if index == -N:
        return [-1]

def calc_score(A):
  score = 0
  for q in list_query:
    if A[q[1]-1]-A[q[0]-1]==q[2]:
      score += q[3]
  return score

max_score = 0
A = [1 for i in range(N)]

while A[0]!=-1:
  max_score = max(max_score, calc_score(A))
  A = next(A)

print(max_score)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as comb

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

ls_q = [tuple(map(int, input().split())) for q in range(Q)]

def calc(c):
    result = 0
    for q in ls_q:
        if c[q[1] - 1] - c[q[0] - 1] == q[2]:
            result += q[3]
            
    return result

ls = [i for i in range(1, M + 1)]

c = comb(ls, N)
max_result = 0
while True:
    try:
        max_result = max(calc(next(c)), max_result)
    except StopIteration:
        break

print(max_result)

Submission status: Accepted

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

import itertools
 
A_kouho = []
for i in itertools.combinations_with_replacement(range(1, m+1), n):
    i = (1,) + i + (m,)
    A_kouho.append(i)
#print(A_kouho)

four_r = []
for j in range(q):
  Q = list(map(int, input().split()))
  four_r.append(Q)
#print(four_r)

max_ = 0
for A in A_kouho:
  sum_ = 0
  for j in four_r:
    #print('%d %d'%(A[j[1]]-A[j[0]],j[2]))
    if A[j[1]]-A[j[0]]==j[2]:
      sum_+=j[3]
    if sum_>max_: max_=sum_
print(max_)

Submission status: Accepted

Solution code:
N, M, Q = [int(s) for s in input().split()]
dat = [[int(s) for s in input().split()] for _ in range(Q)]
A = [0] * N
result = []


def Calc(count):
    global result
    global A
    cnt = 0
    if count == N:
        for d in dat:
            if A[d[1] - 1] - A[d[0] - 1] == d[2]:
                cnt += d[3]
        return cnt
    else:
        max_val = 0
        if count == 0:
            start = 1
        else:
            start = A[count-1]

        for i in range(start, M + 1):
            A[count] = i
            max_val = max(max_val, Calc(count + 1))
        return max_val


print(Calc(0))

Submission status: Accepted

Solution code:
import itertools

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

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

rr = range(1, M + 1)
it = itertools.combinations_with_replacement(rr, N)

M_ans = 0

for A in it:
    ans = 0
    for a, b, c, d in ABCD:
        if A[b - 1] - A[a - 1] == c:
            ans += d

    if ans > M_ans:
        M_ans = ans

print(M_ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,M,Q = inputMap()
	A = []
	for i in range(Q):
		a,b,c,d = inputMap()
		A.append((a,b,c,d))

	retu = []
	for i1 in range(M,0,-1):
		tmp = []
		for i2 in range(M,0,-1):
			if i1 > i2:
				break
			for i3 in range(M,0,-1):
				if i2 > i3:
					break
				for i4 in range(M,0,-1):
					if i3 > i4:
						break
					for i5 in range(M,0,-1):
						if i4 > i5:
							break
						for i6 in range(M,0,-1):
							if i5 > i6:
								break
							for i7 in range(M,0,-1):
								if i6 > i7:
									break
								for i8 in range(M,0,-1):
									if i7 > i8:
										break
									for i9 in range(M,0,-1):
										if i8 > i9:
											break
										for i10 in range(M,0,-1):
											if i9 > i10:
												break
											tmp.append(i1)
											tmp.append(i2)
											tmp.append(i3)
											tmp.append(i4)
											tmp.append(i5)
											tmp.append(i6)
											tmp.append(i7)
											tmp.append(i8)
											tmp.append(i9)
											tmp.append(i10)
											retu.append(tmp[:N])
											tmp = []
	ans = 0
	for i in retu:
		#print(i)
		score = 0
		for vol in A:
			a,b,c,d = vol
			#print("{} {}".format(int(i[b-1]) - int(i[a-1]), c))
			if int(i[b-1]) - int(i[a-1]) == c:
				score += d

		if score > ans:
			ans = score

	print(ans)


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import itertools
n, m, q = map(int, input().split())
li = [list(map(int, input().split())) for _ in range(q)]
ml = list(range(1, m+1))
a_list = list(itertools.combinations_with_replacement(ml,n))
ans_l = []
for l in a_list:
    tmp = 0
    for a, b, c, d in li:
        if l[b-1] - l[a-1] == c:
            tmp += d
    ans_l.append(tmp)
print(max(ans_l))

Submission status: Accepted

Solution code:
import itertools

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

listn = []
for i in range(m):
    listn.append(i+1)
list_ex = list(itertools.combinations_with_replacement(listn, n))

ans = 0
for i in range(len(list_ex)):
    list_ex2 = list_ex[i]
    ans2 = 0
    for j in range(q):
        listi2 = listi[j]
        ai = listi2[0]-1
        bi = listi2[1]-1
        ci = listi2[2]
        if (list_ex2[bi] - list_ex2[ai] == ci):
            ans2 += listi2[3]
    if (ans < ans2):
        ans = ans2

print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M,Q = map(int,input().split())
n_list = list()
l = list()
d = list()
d_sum = list()
for i in range(1,M+1):
    l.append(i)
A_list = list(itertools.combinations_with_replacement(l,N))
for i in range(Q):
    n_list.append(list(map(int,input().split())))
for A in A_list:
    for i in range(Q):
        if A[n_list[i][1]-1]-A[n_list[i][0]-1] == n_list[i][2]:
            d.append(n_list[i][3])
        else:
            d.append(0)
    d_sum.append(sum(d))
    d.clear()
print(max(d_sum))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import itertools
def main():
# 整数の入力
    
    # スペース区切りの整数の入力
    s = [int(x) for x in input().split(' ')]
    n = s[0]
    m = s[1]
    q = s[2]
    t_list = []
    for i in range(q):
        s = [int(x) for x in input().split(' ')]
        t_list.append(s)

    seq = [x for x in range(1, m+1)]
    candidate_list = list(itertools.combinations_with_replacement(seq, n))

    candidate_d_list = []
    candidate_d_list.append(0)
    for candidate in candidate_list:
        d_list = []
        d_list.append(0)

        for t in t_list:
            a = t[0]
            b = t[1]
            c = t[2]
            d = t[3]
            
            if candidate[b-1] - candidate[a-1] == c:
                d_list.append(d)
        candidate_d_list.append(sum(d_list))

    
    print(max(candidate_d_list))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans=[1 for i in range(n)]
nans=0

while ans!=[m for i in range(n)]:
    #print(ans)
    sum=0
    for i in range(q):
        if ans[a[i][1]-1]-ans[a[i][0]-1]==a[i][2]:
            sum+=a[i][3]
    #print(sum)
    nans=max(nans,sum)
    ans[-1]+=1
    while max(ans)>m:
        max_ind=ans.index(m+1)
        ans[max_ind-1]+=1
        ue=ans[max_ind-1]
        for i in range(max_ind,len(ans)):
            ans[i]=ue
sum=0
for i in range(q):
    if ans[a[i][1]-1]-ans[a[i][0]-1]==a[i][2]:
        sum+=a[i][3]
nans=max(nans,sum)

print(nans)

Submission status: Accepted

Solution code:
n, m, q =  list(map(int, input().split()))
aa = []
bb =[]
cc = []
dd =[]
for i in range(q):
    a,b,c,d =  list(map(int, input().split()))
    aa.append(a)
    bb.append(b)
    cc.append(c)
    dd.append(d)

def ev(A):
    s = 0
    for i in range(q):
        if A[bb[i] - 1] - A[aa[i] - 1] == cc[i]:
            s += dd[i]
    return s

A = [0] * n
s = ev(A)
for i0 in range(m):
    for i1 in range(i0, m):
        for i2 in range(i1, m):
            for i3 in range(i2, m):
                for i4 in range(i3, m):
                    for i5 in range(i4, m):
                        for i6 in range(i5, m):
                            for i7 in range(i6, m):
                                for i8 in range(i7, m):
                                    for i9 in range(i8, m):
                                        A = [i0, i1, i2, i3, i4, i5, i6, i7, i8, i9][:n]
                                        s = max([s, ev(A)])
print(s)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement


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

points = []
for A in combinations_with_replacement(range(1, m + 1), n):
    # print(A)
    point = 0
    for a, b, c, d in Q:
        if A[b-1] - A[a-1] == c:
            point += d
    points.append(point)

print(max(points))

Submission status: Accepted

Solution code:
n, m, q = [int(v) for v in input().split()]
a = []
b = []
c = []
d = []
for i in range(q):
    line = [int(v) for v in input().split()]
    a.append(line[0])
    b.append(line[1])
    c.append(line[2])
    d.append(line[3])

ans = 0

def calc(nums):
    ret = 0
    for i in range(q):
        if nums[b[i]-1] - nums[a[i]-1] == c[i]:
            ret += d[i]
    return ret

def solve(n, m, buf):
    if n == 0:
        global ans
        ans = max(ans, calc(buf))
        return

    if buf:
        for i in range(buf[-1], m+1):
            new_buf = buf[:]
            new_buf.append(i)
            solve(n-1, m, new_buf)
    else:
        for i in range(1, m+1):
            new_buf = buf[:]
            new_buf.append(i)
            solve(n-1, m, new_buf)

solve(n, m, [])
print(ans)

Submission status: Accepted

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

import itertools

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


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

for listA in A:
    count=0
    for kumi in abcd:
        a,b,c,d=kumi
        
        if listA[b-1]-listA[a-1]==c:
            count+=d
    ans=max(ans,count)
print(ans)

Submission status: Accepted

Solution code:
n,m,q = map(int, raw_input().split(' '))
reqs= [map(int, raw_input().split(' ')) for _ in range(q)]
max_ = [0]

def dfs(i, cur, n, m, reqs ):
	if n == 0:
		score = 0
		for a,b,c,d in reqs:
			if cur[b-1] - cur[a-1] == c: score += d
		max_[0] = max(max_[0], score)
		return 

	for j in range(i, m+1):
		dfs(j, cur + [j], n-1, m, reqs)

dfs(1, [], n, m, reqs)
print max_[0]

Submission status: Accepted

Solution code:
from sys import stdin,stdout
input=stdin.buffer.readline

ip=[int(x) for x in input().split()]
n=ip[0]
m=ip[1]
q=ip[2]

ai=[]
bi=[]
ci=[]
di=[]
for i in range(q):
	ip=[int(x) for x in input().split()]
	ai.append(ip[0])
	bi.append(ip[1])
	ci.append(ip[2])
	di.append(ip[3])

a=[]
if n==10:
	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):
											a.append([i1,i2,i3,i4,i5,i6,i7,i8,i9,i10])

	ans=0
	for i in range(len(a)):
		m=0
		for j in range(q):
			if a[i][bi[j]-1]-a[i][ai[j]-1]==ci[j]:
				m+=di[j]
		if ans<m:
			ans=m

	print(ans)
elif n==9:
	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):
										a.append([i1,i2,i3,i4,i5,i6,i7,i8,i9])

	ans=0
	for i in range(len(a)):
		m=0
		for j in range(q):
			if a[i][bi[j]-1]-a[i][ai[j]-1]==ci[j]:
				m+=di[j]
		if ans<m:
			ans=m

	print(ans)
elif n==8:
	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):
									a.append([i1,i2,i3,i4,i5,i6,i7,i8])

	ans=0
	for i in range(len(a)):
		m=0
		for j in range(q):
			if a[i][bi[j]-1]-a[i][ai[j]-1]==ci[j]:
				m+=di[j]
		if ans<m:
			ans=m

	print(ans)
elif n==7:
	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):
								a.append([i1,i2,i3,i4,i5,i6,i7])

	ans=0
	for i in range(len(a)):
		m=0
		for j in range(q):
			if a[i][bi[j]-1]-a[i][ai[j]-1]==ci[j]:
				m+=di[j]
		if ans<m:
			ans=m

	print(ans)
elif n==6:
	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):
							a.append([i1,i2,i3,i4,i5,i6])

	ans=0
	for i in range(len(a)):
		m=0
		for j in range(q):
			if a[i][bi[j]-1]-a[i][ai[j]-1]==ci[j]:
				m+=di[j]
		if ans<m:
			ans=m

	print(ans)
elif n==5:
	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):
						a.append([i1,i2,i3,i4,i5])

	ans=0
	for i in range(len(a)):
		m=0
		for j in range(q):
			if a[i][bi[j]-1]-a[i][ai[j]-1]==ci[j]:
				m+=di[j]
		if ans<m:
			ans=m

	print(ans)
elif n==4:
	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):
					a.append([i1,i2,i3,i4])

	ans=0
	for i in range(len(a)):
		m=0
		for j in range(q):
			if a[i][bi[j]-1]-a[i][ai[j]-1]==ci[j]:
				m+=di[j]
		if ans<m:
			ans=m

	print(ans)
elif n==3:
	for i1 in range(1,m+1):
		for i2 in range(i1,m+1):
			for i3 in range(i2,m+1):
				a.append([i1,i2,i3])

	ans=0
	for i in range(len(a)):
		m=0
		for j in range(q):
			if a[i][bi[j]-1]-a[i][ai[j]-1]==ci[j]:
				m+=di[j]
		if ans<m:
			ans=m

	print(ans)
elif n==2:
	for i1 in range(1,m+1):
		for i2 in range(i1,m+1):
			a.append([i1,i2])

	ans=0
	for i in range(len(a)):
		m=0
		for j in range(q):
			if a[i][bi[j]-1]-a[i][ai[j]-1]==ci[j]:
				m+=di[j]
		if ans<m:
			ans=m

	print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
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=[]
def saiki(num,lis):
    if num==N:
        temp=0
        for a,b,c,d in q:
            if lis[b-1]-lis[a-1]==c:
                temp+=d
        ans.append(temp)
    else:
        for i in range(lis[-1],M+1):
            saiki(num+1,lis+[i])
saiki(0,[1])

print(max(ans))

Submission status: Accepted

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

import itertools
a = range(1, M+1)
for set_A in itertools.combinations_with_replacement(a, N):
    A = list(set_A)
    n = 0
    for i in range(Q):
        if A[b[i][1]-1] - A[b[i][0]-1] == b[i][2]:
            n += b[i][3]
    ans = max(ans, n)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

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

dfs([0])

ans = 0
for p in path:
    score = 0
    for a, b, c, d in points:
        if p[b] - p[a] == c:
            score += d
    ans = max(ans, score)
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools

def main():
    input = sys.stdin.readline
    N, M, Q = map(int, input().split())
    data = range(1, M+1)
    A = list(itertools.combinations_with_replacement(range(1, M+1), N))
    l = []
    m = 0
    for _ in range(Q):
        a, b, c, d = map(int, input().split())
        l.append([a, b, c, d])
    for a_list in A:
        tmp = 0
        for i in l:
            if a_list[i[1] -1] - a_list[i[0] - 1] == i[2]:
                tmp += i[3]
        if tmp > m:
            m = tmp
    return m


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def make_arr(x, arr):
    if len(arr) == n:
        pattern.append(arr)
    else:
        for i in range(x, m + 1):
            make_arr(i, arr + [i])

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

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

ans = 0
for p in pattern:
    point = 0
    for a, b, c, d in query:
        a -= 1
        b -= 1
        if  (p[b] - p[a]) == c:
            point += d
    ans = max(ans, point)
print(ans)

Submission status: Accepted

Solution code:

def main():
    N, M, Q = map(int, input().split())  # 入力

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

    A = [1]*N

    flg = True

    s = 0
    ans = None

    while flg:
        # print(A)
        t_s = rtn_score(A, kumi)
        if t_s > s:
            s = t_s
            ans = A
        for i in range(N):
            if A[N - 1 - i] < M:
                A[N - 1 - i] += 1
                break
            else:
                if A[N - 1 - i - 1] < M:
                    A[N - 1 - i - 1] += 1
                    for j in range(i+1):
                        A[N - 1 - j] = A[N - 1 - i - 1]
                    break
            if i == N - 1:  # last
                flg = False

    print(s)


def rtn_score(A, kumi):
    tmp_s = 0
    for k in kumi:
        # print(k)
        # print(k[1])
        if A[k[1]-1] - A[k[0]-1] == k[2]:
            tmp_s += k[3]
    return tmp_s


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

ans = 0
for c in comb:
    p = 0
    for l in lst:
        if c[l[1] - 1] - c[l[0] -1] == l[2]:
            p += l[3]
    ans = max(ans, p)
print(ans)

Submission status: Accepted

Solution code:
import random as rng
import itertools as it
import collections as col
import heapq as hq
import sys
import copy as cp
sys.setrecursionlimit(10**9)


def dump_impl(*objects):
    print(*objects, file=sys.stderr)


def dump_dummy(*objects):
    pass


dump = dump_impl if "DEBUG" in sys.argv else dump_dummy

N, M, Q = map(int, input().split())
a = [0]*Q
b = [0]*Q
c = [0]*Q
d = [0]*Q
for i in range(Q):
    ai, bi, ci, di = map(int, input().split())
    a[i], b[i], c[i], d[i] = ai, bi, ci, di

dump(N, M, Q)
dump(a)
dump(b)
dump(c)
dump(d)

ans = 0


for A in it.combinations_with_replacement(range(1, M+1), N):
    A = list(A)
    x = [0]

    for i in range(Q):
        if A[b[i] - 1] - A[a[i] - 1] == c[i]:
            x.append(d[i])
    ans = max(ans, sum(x))
print(ans)

Submission status: Accepted

Solution code:
import itertools
n, m, q = map(int, input().split())
a_tmp = b_tmp = c_tmp = d_tmp = 0
a = []
b = []
c = []
d = []
for i in range(q):
    a_tmp, b_tmp, c_tmp, d_tmp = map(int, input().split())
    a.append(a_tmp)
    b.append(b_tmp)
    c.append(c_tmp)
    d.append(d_tmp)
max = 0
for i in itertools.combinations_with_replacement(range(m), n):
    s = 0
    for j in range(q):
        if i[b[j]-1] - i[a[j]-1] == c[j]:
            s = s + d[j]
    if s > max:
        max = s
print(max)

Submission status: Accepted

Solution code:
import itertools
n, m, q = map(int, input().split())
l = []
for i in range(q):
    a, b, c, d = map(int, input().split())
    l.append([a-1, b-1, c, d])
ll = [i for i in range(1, m+1)]
h = itertools.combinations_with_replacement(ll, n)
ans = 0
for v in h:
    vl = list(v)
    cnt = 0
    for i in range(q):
        ai, bi, ci, di = l[i]
        if vl[bi] - vl[ai] == ci:
            cnt += di
    ans = max(ans, cnt) 
print(ans)

Submission status: Accepted

Solution code:
ans = 0


def main():
    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] * N

    def check(A, i):
        global ans
        if i + 1 == N:
            ans = max(point_check(A), ans)
            return
        for j in range(A[i], M+1):
            A[i+1] = j
            check(A, i + 1)

    def point_check(arr):
        pt = 0
        for i in range(Q):
            if arr[b[i]-1] - arr[a[i]-1] == c[i]:
                pt += d[i]
        return pt

    for i in range(1, M + 1):
        A[0] = i
        check(A, 0)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

n, m, q = map(int, input().split())
comb = list(combinations_with_replacement(range(1, m+1), n))
ans = [0] * len(comb)
for _ in range(q):
    a, b, c, d = map(int, input().split())
    for i in range(len(comb)):
        if comb[i][b-1] - comb[i][a-1] == c:
            ans[i] += d
print(max(ans))

Submission status: Accepted

Solution code:
n, mm, 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())
import itertools
td = []
ttd = []

m = []
for i in range(1,mm+1):
    m.append(i)

s = list(itertools.combinations_with_replacement(m, n))
for j in range(len(s)):
    for i in range(q):
        if s[j][b[i]-1] - s[j][a[i]-1] == c[i]:
            td.append(d[i])
    ttd.append(sum(td))
    td = []
if ttd==[]:
    print(0)
else:
    print(max(ttd))

Submission status: Accepted

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

S=0
temp=0
A=[1] * N

while A[0]!=M:
  for k in range(Q):
    if A[b[k]-1]-A[a[k]-1]==c[k]:
      temp+=d[k]
  if temp>S:
    S=temp
  temp=0
  for i in range(1,N+1):
    if A[N-i]!=M:
      for j in range(1,i+1):
        A[N-j]=A[N-i]+1
      break

A=[M]*N
for k in range(Q):
  if A[b[k]-1]-A[a[k]-1]==c[k]:
    temp+=d[k]
if temp>S:
  S=temp
  
print(S)

Submission status: Accepted

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

alist=[]

def saiki(tn,a,tlist):
    global alist
    global m
    global n
    if tn == n:
        for i in range(a,m+1):
            tmplist=[]
            tmplist=copy.deepcopy(tlist)
            tmplist.append(i)
            alist.append(tmplist)
    else:
        for i in range(a,m+1):
            tmplist=[]
            tmplist=copy.deepcopy(tlist)
            tmplist.append(i)
            saiki(tn+1,i,tmplist)

saiki(1,1,[])

summax=0
for a in alist:
    tmpsum=0
    for ele in intlist:
        if a[ele[1]-1]-a[ele[0]-1] == ele[2]:
            tmpsum += ele[3]
    if tmpsum > summax:
        summax=tmpsum

print(summax)

Submission status: Accepted

Solution code:
import itertools

# 入力
n, m, q = (int(each) for each in input().split())
a = []
for each in range(q):
    a.append([int(each) for each in input().split()])

# Aのリストを生成する
l = [i+1 for i in range(m)]
p = itertools.combinations_with_replacement(l, n)
p = set([tuple(sorted(list(v))) for v in p])

# print(p)
# Aのリストそれぞれについて、スコアを計算する
scorelist = []
for eachA in p:
    score = 0
    for linei in a:
        # print('eachA', eachA)
        # print('linei', linei)
        if eachA[linei[1]-1] - eachA[linei[0]-1] == linei[2]:
            score += linei[3]
    scorelist.append(score)

print(max(scorelist))