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 as itr
N, M, Q = map(int, input().split())
req = []
for i in range(Q):
    a, b, c, d = map(int, input().split())
    a -= 1; b -= 1;
    req.append((a, b, c, d))


ans = -1
for pattern in itr.combinations_with_replacement(range(1, M+1), N):
    A = pattern
    tmp = 0
    for reqirements in req:
        a, b, c, d = reqirements
        if A[b] - A[a] == c:
            tmp += d

        ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
import itertools

def main():
    N, M, Q = list(map(int, input().split()))
    a = []
    b = []
    c = []
    d = []

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

    ans = 0
    for A in list(itertools.combinations_with_replacement(range(1, M+1), N)):
#    print(A)                                                                                          
        score = 0
        for i in range(Q):
            if A[b[i]-1] - A[a[i]-1] == c[i]:
                score += d[i]
        if ans < score:
            ans = score

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools

N, M, Q = list(map(int, input().split()))
a = []
b = []
c = []
d = []

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

ans = 0
for A in list(itertools.combinations_with_replacement(range(1, M+1), N)):
#    print(A)                                                                                          
    score = 0
    for i in range(Q):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            score += d[i]
    if ans < score:
        ans = score

#    print(A, score)                                                                                   
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

#重複組み合わせ
ans = 0
for i in combinations_with_replacement(range(m),n):
    t = 0
    for a,b,c,d in L:
        if i[b-1] - i[a-1] == c:
            t += d
    ans = max(ans,t)

print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m,q=map(int,input().split())
d=[list(map(int,input().split())) for i in range(q)]
ans=0
for i in list(itertools.combinations_with_replacement(list(range(1,m+1)), n)):
  a=list(i)
  hantei=0
  for j in range(q):
    if (a[d[j][1]-1]-a[d[j][0]-1])==d[j][2]:
      hantei+=d[j][3]
  ans=max(ans,hantei)
print(ans)

Submission status: Accepted

Solution code:
#C - Many Requirements
#再帰関数(n重のfor文)
N,M,Q = map(int,input().split())
abcd = []
for _ in range(Q):
    a,b,c,d = map(int,input().split())
    abcd.append((a,b,c,d))
max_score = 0
def dfs(A):
    global max_score
    if len(A) == N:
        #処理
        score = 0
        for ai,bi,ci,di in abcd:
            if A[bi-1] -A[ai-1] == ci:
                score += di
        return score
    #一つ前の値を保持
    if len(A) >= 1:
        prev_last = A[-1]
    else:
        prev_last = 1
    #1つ前の値より大きい値の範囲
    for i in range(prev_last,M+1):
        A.append(i)
        max_score = max(max_score,dfs(A))
        A.pop()
    return max_score#ループの途中のdfs (len(A) != N のとき) に値を返す
dfs([])
print(max_score)

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

# スコア計算
def score(A):
    tmp = 0
    for ai, bi, ci, di in zip(a, b, c, d):
        if A[bi] - A[ai] == ci:
            tmp += di
    return tmp

# DFS
def dfs(A):
    if len(A) == N:
        return score(A) # 数列 A のスコアを返す
    res = 0
    prev_last = A[-1] if len(A) > 0 else 0
    for v in range(prev_last, M):
        A.append(v)
        res = max(res, dfs(A)) # 再帰呼出しながら、スコア最大値も更新
        A.pop()
    return res

# 求める
print(dfs([]))

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

L = list(itertools.combinations_with_replacement(range(1,M+1), N))
p_list =  []

for l in L :
    point = 0
    for x in X :
        if l[x[1]-1] - l[x[0]-1] == x[2] :
            point += x[3]
            
    p_list.append(point)

# print(X)
# print(L)
# print(p_list)
print(max(p_list))

Submission status: Accepted

Solution code:
import copy

def main():
	N, M, Q = [int(n) for n in input().split(" ")]
	q = [[int(a) for a in input().split(" ")] for i in range(Q)]
	all_series = get_series(N, M)
	points = [0]
	for l in all_series:
		points.append(get_score(l, q))
	print(max(points))

def get_score(l, q):
	return sum([q[i][3] if l[q[i][1] - 1] - l[q[i][0] - 1] == q[i][2] else 0 for i in range(len(q))])

def get_series(N, M):
	# N: number of elms
	# M: upper limit of val of elm
	all_series = []
	checked = [[0] * M for i in range(N)]
	to_check = [[0, j + 1] for j in range(M)]
	series = [0 for k in range(N)]
	while len(to_check) > 0:
		checking = to_check.pop(-1)
		series[checking[0]] = checking[1]
		if checking[0] == N - 1:
			l = copy.deepcopy(series)
			all_series.append(l)
		else:
			to_check.extend([[checking[0] + 1, k] for k in range(checking[1], M + 1)])
	return all_series

main()

Submission status: Accepted

Solution code:
import itertools

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

    pattern = itertools.combinations_with_replacement(range(1, m+1), n)
    best = 0
    for p in pattern:
        cost = 0
        for l in all_list:
            if p[l[1]-1] - p[l[0]-1] == l[2]:
                cost += l[3]
        if cost > best:
            best = cost
    print(best)

abc165c_many_requirements()

Submission status: Accepted

Solution code:
import itertools
n,m,q = map(int,input().split())
abcd = [list(map(int,input().split())) for _ in range(q)]
maxpt = 0
for lis in itertools.combinations_with_replacement(range(1, m+1), n):
    forpt = 0
    for i in range(q):
        if lis[abcd[i][1]-1] - lis[abcd[i][0]-1] == abcd[i][2]:
            forpt += abcd[i][3]
    maxpt = max(maxpt,forpt)
print(maxpt)

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
def dfs(seq):
    u=0
    if len(seq)==n:
        ans=0
        for a,b,c,d in data:
            if seq[b-1]-seq[a-1]==c:
                ans+=d
        return ans
    else:
        for i in range(seq[-1],m+1):
            seq_next=seq.copy()
            seq_next.append(i)
            u=max(u,dfs(seq_next))
        return u

data=[]
for _ in range(q):
    A=list(map(int,input().split()))
    data.append(A)
print(dfs([1]))

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
def dfs(seq):
    u=0
    if len(seq)==n:
        ans=0
        for a,b,c,d in data:
            if seq[b-1]-seq[a-1]==c:
                ans+=d
        return ans
    else:
        for i in range(seq[-1],m+1):
            seq_next=seq+[i]
            u=max(u,dfs(seq_next))
        return u

data=[]
for _ in range(q):
    A=list(map(int,input().split()))
    data.append(A)
print(dfs([1]))

Submission status: Accepted

Solution code:
import itertools
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,M,Q=mi()
    X = []
    for i in range(Q):
        a,b,c,d = mi()
        X.append((a,b,c,d))

    ans = 0
    num_list = list(range(1,M+1))
    for _nums in itertools.combinations_with_replacement(num_list, N):
        nums = list(_nums)
        D = 0
        for j in range(Q):
            a,b,c,d = X[j]
            if nums[b-1] - nums[a-1] == c: 
                D += d
        
        ans = max(ans,D)

    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools
n, m, q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(q)]
l = list(itertools.combinations_with_replacement(range(1, m+1), n))
ans = 0
for i in l:
    w = 0
    for j in abcd:
        if i[j[1]-1] - i[j[0]-1] == j[2]:
            w += j[3]
    ans = max(ans, w)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import combinations_with_replacement
def main():
    n, m, q = map(int, input().split())
    xs = []
    for i in range(q):
        xs.append(list(map(int, input().split())))
    max = 0
    for suretu in combinations_with_replacement(range(1, m + 1), n):
        wa = 0
        for x in xs:
            a, b, c, d = x
            if suretu[b - 1] - suretu[a - 1] == c:
                wa += d
        if wa > max:
            max = wa
    print(max)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def dfs(s):
    global ans
    if len(s) == n:
        cnt = 0
        for i in range(q):
            if s[abcd[i][1]-1]-s[abcd[i][0]-1] == abcd[i][2]:
                cnt += abcd[i][3]
        ans = max(ans, cnt)
        return
    last = 1
    if len(s) > 0:
        last = s[-1]
    for i in range(last, m+1):
        dfs(s+[i])
    return

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

Submission status: Accepted

Solution code:
import sys
N, M, Q = map(int, input().split())
abcd = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]
ans = 0
done = set()
todo = [(i,) for i in range(1, M + 1)]
while todo:
    A = todo.pop()
    done.add(A)
    if len(A) == N:
        total = 0
        for a, b, c, d in abcd:
            if A[b-1] - A[a-1] == c:
                total += d
        ans = max(ans, total)
        continue
    for i in range(A[-1], M + 1):
        nA = A + (i,)
        if not nA in done:
            todo.append(nA)
print(ans)

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])
def dfs(i):
  if i==0:
    alist=[]
    for k in range(m):
      alist.append([k+1])
    return alist
  elif i>0:
    blist=[]
    for k in dfs(i-1):
      last=k[-1]
      for l in range(last,m+1):
        clist=k.copy()
        clist.append(l)
        blist.append(clist)
    return blist
ans=0
for alist in dfs(n-1):
  cnt=0
  for i in range(q):
    if alist[abcd[i][1]-1]-alist[abcd[i][0]-1]==abcd[i][2]:
      cnt+=abcd[i][3]
  ans=max(ans,cnt)
print(ans)

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])
def dfs(i,j):
  if i==0:
    alist=[]
    for k in range(j):
      alist.append([k+1])
    return alist
  elif i>0 and i<=n:
    blist=[]
    for k in dfs(i-1,j):
      last=k[-1]
      for l in range(last,j+1):
        clist=k.copy()
        clist.append(l)
        blist.append(clist)
    return blist
ans=0
for alist in dfs(n-1,m):
  cnt=0
  for i in range(q):
    if alist[abcd[i][1]-1]-alist[abcd[i][0]-1]==abcd[i][2]:
      cnt+=abcd[i][3]
  ans=max(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
#12653415
#わからんが、とてもきれいですね

N, M, Q = list(map(int, input().split()))
 
conditions = [list(map(int, input().split())) for _ in range(Q)]
 
def dfs(A, max_a):
    if len(A) == N:
        num = 0
        for a, b, c, d in conditions:
            if A[b-1] - A[a-1] == c:
                num += d
        return num
    ans = 0
    for i in range(max_a, M+1):
        ans = max(ans, dfs(A + [i], i))
    return ans
 
print(dfs([1], 1))

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

A = list(combinations_with_replacement(list(range(1, M+1)), N))
Alist = [list(a) for a in A]

#print(Alist)

Max = 0

for a in Alist:
    cost = 0
    for t in T:
        if a[t[1]-1] - a[t[0]-1] == t[2]:
            cost += t[3]
    if cost > Max:
        Max = cost
print(Max)

Submission status: Accepted

Solution code:
import itertools
import sys

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

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

a = itertools.combinations_with_replacement(range(1,M+1), N)
a = list(a)
Ans = 0
for i in range(len(a)):
  Ans = max(Ans,score(abcd,list(a[i])))
            
print(Ans)

Submission status: Accepted

Solution code:
import itertools

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

seisu_list = []

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

M_list = [i for i in range(1,M+1)]
A_list = list(itertools.combinations_with_replacement(M_list,N))
#print(A_list)
ans = 0

for i in range(len(A_list)):
    ans_temp = 0
    for j in range(Q):
        if A_list[i][seisu_list[j][1]-1] - A_list[i][seisu_list[j][0]-1] == seisu_list[j][2]:
            ans_temp += seisu_list[j][3]
            ans = max(ans, ans_temp)
print(ans)

Submission status: Accepted

Solution code:
import itertools
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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

  
def main(n, m, abcd):
    p = itertools.combinations_with_replacement(range(1, m+1), n)
    L = list(p)
    ans = 0
    for A in L:
        ans = max(ans, score(list(A)))
    return ans


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

print(main(n, m, abcd))

Submission status: Accepted

Solution code:
target = []
def dfs(A):
    if len(A) == N:
        tmp = 0
        for a, b, c, d in arr:
            if A[b-1] - A[a-1] == c:
                tmp += d
        target.append(tmp)
        return
    start = 1
    if len(A) != 0:
        start = A[-1]
    for v in range(start,M+1):
        A.append(v)
        dfs(A)
        A.pop()
N, M, Q = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(Q)]
dfs([])
print(max(target))

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())

def solve():
    N, M, Q = MAP()
    A = [LIST() for _ in range(Q)]

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

if __name__ == '__main__':
    solve()

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 A in combinations_with_replacement(range(1,M+1),N):
  score = 0
  for i in range(Q):
    a,b,c,d=abcd[i]
    if A[b-1]-A[a-1]==c:
      score += d
  ans = max(ans,score)
  
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

ans=0
for A in itertools.combinations_with_replacement([m for m in range(1,M+1)], N):
  ans2=0
  for (a,b,c,d) in ABCD:
    if A[b-1]-A[a-1]==c:
      ans2+=d
  ans=max(ans, ans2)
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

ans=0
t=[m for m in range(1,M+1)]
for A in itertools.combinations_with_replacement(t, N):
  ans2=0
  for (a,b,c,d) in ABCD:
    if A[b-1]-A[a-1]==c:
      ans2+=d
  ans=max(ans, ans2)
print(ans)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def dfs(seq):
    ans = 0
    if len(seq) == n:
        kou = 0
        for u in data:
            if seq[u[1]-1] - seq[u[0]-1] == u[2]:
                kou+=u[3]
        return kou
    else:#len(seq)==N-1からの遷都を考えると良い
        for i in range(seq[-1], m+1):
            seq_next=seq+[i]
            ans = max(ans, dfs(seq_next))
        return ans

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

score = dfs([1])
print(score)

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())
    
def dfs(n_list, o, l, L):
    if o+l==0:
        num = 1
        pos = 0
        
        L_child = [0]*N
        for i in range(N+M-1):
            if n_list[i]==1:
                num += 1
            else:
                L_child[pos] = num
                pos += 1
        L.append(L_child)
    
    if o>=1:
        n_list[N+M-o-l-1] = 0
        dfs(n_list, o-1,l, L)
    if l>=1:
        n_list[N+M-o-l-1] = 1
        dfs(n_list, o, l-1, L)
    
A = [0]*(N+M-1)
L =[]
dfs(A,N,M-1,L)

ans = 0
for i in L:
    score = 0
    for j in range(Q):
        if i[b[j]-1]-i[a[j]-1]==c[j]:
            score += d[j]

    if score > ans:
        ans = score

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import itertools
def main():
    n, m, q = map(int, input().split())
    matrix = []
    for _ in range(q):
        row = list(map(int, input().split()))
        matrix.append(row)
    # print(matrix)
    A = list(range(1, m+1))
    ans = 0
    for tmp_A in itertools.combinations_with_replacement(A, n):
        tmp_A = sorted(list(tmp_A))
        tmp_ans = 0
        for row in matrix:
            # print("row", row)
            # print("tmp_A", tmp_A)
            tmp = tmp_A[row[1] - 1] - tmp_A[row[0]- 1]
            if row[2] == tmp:
                tmp_ans += row[3]
        if tmp_ans >= ans:
            ans = tmp_ans
            
    print(ans)
    
main()

Submission status: Accepted

Solution code:
# 素朴に実装
N, M, Q = [int(i) for i in input().split()]
B = [[0, 0, 0, 0] for i in range(Q)]
for i in range(Q):
    B[i][0], B[i][1], B[i][2], B[i][3] = [int(j) for j in input().split()]
MAXC = [0]

def dfs(A, pre):
    # 終端条件 --- 10 重ループまで回したら処理して打ち切り
    if len(A) == N:
        counter = 0
        for i in range(Q):
            if A[B[i][1]-1] - A[B[i][0]-1] == B[i][2]:
                counter += B[i][3]
        if MAXC[0] < counter:
            MAXC[0] = counter
        return 
    for v in range(pre, M+1):
        A.append(v)
        dfs(A, v)
        A.pop() 
dfs([], 1)
print(MAXC[0])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# スペース区切りの整数の入力

def dfs(seq):
    ans = 0
    if len(seq) == N:
        score_ret = 0
        for a, b, c, d in data:
            if seq[b-1] - seq[a-1] == c:
                score_ret += d
        return score_ret
    else:
        for i in range(seq[-1], M+1):
            seq_next = seq + (i,)
            score = dfs(seq_next)
            ans = max(ans, score)
    
    return ans

# スペース区切りの整数の入力
N, M, Q = map(int, input().split())
#配列の入力
data = [list(map(int, input().split())) for _ in range(Q)]

ans = -1
score = dfs((1,))
ans = max(ans, score)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# スペース区切りの整数の入力

from collections import deque

def calc(seq):
    score = 0
    for a, b, c, d in data:
        if seq[b-1] - seq[a-1] == c:
            score += d
    return score

# スペース区切りの整数の入力
N, M, Q = map(int, input().split())
#配列の入力
data = [list(map(int, input().split())) for _ in range(Q)]

ans = -1

que = deque()

for i in range(1, M+1):
    que.append([i])


while que:
    seq = que.popleft()

    if len(seq) == N:
        score = calc(seq)
        ans = max(ans, score)
    else:
        for i in range(seq[-1], M+1):
            seq_next = seq + [i]
            que.append(seq_next)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# スペース区切りの整数の入力

from itertools import combinations_with_replacement as comb_rplc

# スペース区切りの整数の入力
N, M, Q = map(int, input().split())
#配列の入力
data = [list(map(int, input().split())) for _ in range(Q)]

ans = -1

for seq in comb_rplc(range(1, M+1), N):
    score = 0
    for a, b, c, d in data:
        if seq[b-1] - seq[a-1] == c:
            score += d
    
    ans = max(ans, score)

print(ans)

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
e=[list(map(int,input().split())) for _ in range(q)]
ans=0
for i in range(1<<(m+n)):
  a=[1]
  for j in range(m+n):
    if (i>>j)&1:a[-1]+=1
    else:a+=[a[-1]]
    if a[-1]>m:
      flag=0
      break
    if len(a)>n:
      flag=1
      break
  else:flag=1
  if flag==0 or len(a)<n:continue
  cnt=0
  for s,t,u,v in e:
    if a[t-1]-a[s-1]==u:cnt+=v
  ans=max(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
def dfs(seq):
    ans = 0

    if len(seq) == n:
        score = 0
        for a, b, c, d in req:
            if seq[b-1] - seq[a-1] == c:
                score += d
        return score
    else:
        for i in range(seq[-1], m+1):
            next_seq = seq + (i,)
            score = dfs(next_seq)
            ans = max(ans, score)
    return ans

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

print(dfs((1,)))

Submission status: Accepted

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

def func(a):
    if a[-1] != m: 
        a[-1] += 1 
        return a
    else: 
        d = n - 1
        while d > 0 and a[d] == m:
            d = d - 1 
        if d < 0:
            return a
        else: 
            a[d] += 1
            for x in range(d,n): 
                a[x] = a[d]
            return a
            
ans = 0
a[-1] = 0
while sum(a) != n*m:
    func(a)
    di = 0
    for i in range(q): 
        if a[abcd[i][1]-1] - a[abcd[i][0]-1] == abcd[i][2]: 
            di += abcd[i][3] 
    ans = max(ans, di) 
print(ans)

Submission status: Accepted

Solution code:
from _collections import deque

def cacl(seq):
    score = 0
    for a, b, c, d in req:
        if seq[b-1] - seq[a-1] == c:
            score += d
    return score

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

ans = 0
que = deque()

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

while que:
    seq = que.popleft()

    if len(seq) == n:
        score = cacl(seq)
        ans = max(ans, score)
    else:
        for i in range(seq[-1], m + 1):
            seq_next = seq + [i]
            que.append(seq_next)
print(ans)

Submission status: Accepted

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

ans = 0

for seq in comb_rplc(range(1,m+1),n):
    now = 0
    for a, b, c, d in req:
        if seq[b-1] - seq[a-1] == c:
            now += d
    ans = max(ans, now)

print(ans)

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
query=[]
for _ in range(q): query.append(list(map(int,input().split())))
ans=0
def rec(a):
    if len(a)==n+1:
        temp=0
        for qu in query:
            if a[qu[1]]-a[qu[0]]==qu[2]: temp+=qu[3]
        global ans
        ans=max(ans,temp)
        return
    for i in range(a[-1],m+1):
        cp=a[:]
        cp.append(i)
        rec(cp)
rec([1])
print(ans)

Submission status: Accepted

Solution code:
def main():
    import itertools
    n,m,q = map(int,input().split())
    Q = []
    for i in range(q):
        Q.append(list(map(int,input().split())))
    cmb = [i for i in range(1,m+1)]
    ans = 0
    for que in itertools.combinations_with_replacement(cmb,n):
        m = 0
        for i in range(q):
            [a,b,c,d] = Q[i]
            if que[b-1]-que[a-1]==c:
                m += d
        if m>ans:
            ans = m
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

n,m,q = lr()
abcd = [lr() for i in range(q)]
def getAns(s, num, l):
    if l == n:
        ret = 0
        for a,b,c,d in abcd:
            a-=1
            b-=1
            if s[b]-s[a] == c:
                ret+=d
        return ret
    else:
        ret = 0
        for i in range(num, m+1):
            tmp = s.copy()
            tmp.append(i)
            ret = max(ret, getAns(tmp, i, l+1))
        return ret
print(getAns([], 1, 0))

Submission status: Accepted

Solution code:
n, m, q = list(map(int, input().split()))
from collections import deque
ans = 0
def calc(seq):
    score = 0
    for a, b, c, d in req:
        if seq[b-1] - seq[a-1] == c:
            score+= d
    return score
req = [list(map(int, input().split())) for i in range(q)]

que = deque()

for h in range(1, m+1):
    que.append([h])

while que:
    seq = que.popleft()
    if len(seq) == n:
        score = calc(seq)
        ans = max(ans, score)
    else:
        for i in range(seq[-1], m+1):
            seq_next = seq + [i]
            que.append(seq_next)

print(ans)

Submission status: Accepted

Solution code:
L=[]
def make_list(n,m,p,l):
  if n==0:
    L.append(l)
  else:
    for i in range(p,m+1):
      make_list(n-1,m,i,l+[i])
  
N,M,Q = map(int,input().split())
T=[tuple(map(int,input().split())) for _ in range(Q)]
ans=0
make_list(N,M,1,[])
for l in L:
  tmp=0
  for a,b,c,d in T:
    if l[b-1]-l[a-1]==c:
      tmp+=d
  ans=max(ans,tmp)
print(ans)

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

from itertools import combinations_with_replacement

ans = 0

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

print(ans)