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())
li = [i for i in range(1,m+1)]
lin = []

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

from itertools import combinations_with_replacement
li = list(combinations_with_replacement(li, n))
ma = 0

for i in li:
    point = 0
    for j in lin:
        a,b,c,d = j
        a -= 1
        b -= 1
        if i[b]-i[a] == c:
            point += d
    ma = max(point,ma)

print(ma)

Submission status: Accepted

Solution code:
#abc165c
import itertools
n,m,q=map(int,input().split())
l=list(itertools.combinations_with_replacement(range(1,m+1),n))
res=[0]*len(l)
for i in range(q):
 a,b,c,d=map(int,input().split())
 for j,x in enumerate(l):
  if x[b-1]-x[a-1]==c:
   res[j]+=d
print(max(res))

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
abcd = [tuple(map(int, input().split())) for _ in range(Q)]
ans = 0
def calc(p):
    ret = 0
    for a, b, c, d in abcd:
        a, b = a-1, b-1
        if p[b] - p[a] == c:
            ret += d
    return ret

def dfs(a, d):
    global ans
    if d == N:
        ans = max(ans, calc(a))
        return
    for i in range(a[-1], M+1):
        dfs(a+[i], d+1)

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

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 pat in combinations_with_replacement(range(1, m + 1), n):
    score = 0
    for a, b, c, d in abcd:
        a -= 1
        b -= 1
        if pat[b] - pat[a] == c:
            score += d

    ans = max(ans, score)

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
N,M,Q = map(int,input().split())
B = []
for j in range(Q):
    b = list(map(int,input().split()))
    B.append(b)
cmax = 0
for k in range(1,N+1):
    for x in combinations(range(1,M+1),k):
        for y in combinations(range(N-1),k-1):
            A = [0 for _ in range(N)]
            curx = 0
            cury = 0
            for i in range(N):
                if cury==k-1 or i<=y[cury]:
                    A[i]=x[curx]
                else:
                    cury += 1
                    curx += 1
                    A[i] = x[curx]
            cnt = 0
            for j in range(Q):
                a,b,c,d = B[j]
                if A[b-1]-A[a-1]==c:
                    cnt += d
            cmax = max(cmax,cnt)
print(cmax)

Submission status: Accepted

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

import itertools
ans = -1
for C in itertools.combinations_with_replacement(range(m), n):
    temp = 0
    for i in range(q):
        a, b, c, d = X[i]
        if C[b]-C[a] == c:
            temp += d
    ans = max(ans, temp)
print(ans)

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


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

Submission status: Accepted

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

'''
1.数列を生成する。
2.配列ごとに得点を求める。
'''
def judge(L):
    score = 0
    for i in range(q):
        check = L[b[i] - 1] - L[a[i] - 1]
        if check == c[i]:score += d[i]

    return score

def dfs(L):
    global score
    if len(L) == n:
        temp = judge(L)
        if temp > score:score = temp
        return #長さnの時ここより下に行かないようにする

    start = L[-1] if len(L) != 0 else 1
    for v in range(start, m + 1):
        L.append(v)
        dfs(L)
        L.pop()


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

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as cbr
N,M,Q = list(map(int, input().split()))
X = []
for _ in range(Q):
  X.append(list(map(int, input().split())))
  
ans = -1
for p in cbr(range(1,M+1), N):
  wk = 0
  for x in X:
    a,b,c,d = x
    if p[b-1] - p[a-1] == c:
      wk += d
  ans = max(wk,ans)
  
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import combinations_with_replacement

input = stdin.readline
N,M,Q = map(int, input().split())
numlist = [i for i in range(1,M+1)]
A = [0]*(Q+1)
B = [0]*(Q+1)
C = [0]*(Q+1)
D = [0]*(Q+1)
for q in range(1,Q+1):
    A[q],B[q],C[q],D[q] = map(int, input().split())

maxscore = 0
for tpl in combinations_with_replacement(numlist,N):
    score = 0
    for q in range(1,Q+1):
        if tpl[B[q]-1] - tpl[A[q]-1] == C[q]:
            score += D[q]
    maxscore = max(maxscore, score)
print(maxscore)

Submission status: Accepted

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

lst = []
for i in range(Q):
  lst.append(list(map(int, input().split())))
  
  
import itertools

## product 順番あり 重複あり（全て）
## premutations 順番あり 重複なし
## combinations 順番なし　重複なし
## combinations_with_replacement 順番なし　重複あり

A_pattern = itertools.combinations_with_replacement(range(1, M+1), N)
ans = 0

for a in A_pattern:
  point = 0
  
  for l in lst:
    if a[l[1]-1] - a[l[0]-1] == l[2]:
      point += l[3]
      
  if ans < point:
    ans = point
    
print(ans)

Submission status: Accepted

Solution code:
import copy

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

def dfs(count, pre, ls):
    if count == N:
        temp = copy.copy(ls)
        num.append(temp)
        return

    for n in range(pre, M+1):
        ls[count] = n
        dfs(count+1, n, ls)
        ls[count] = 0

num = []
ls = [0] * N
dfs(0, 1, ls)

q = [[int(i) for i in input().split()] for j in range(Q)]
ans = 0
for i in range(len(num)):
    n = num[i]
    score = 0
    for j in range(Q):
        a, b, c, d = q[j]
        if n[b-1] - n[a-1] != c:
            continue
        score += d
    else:
        ans = max(ans, score)

print(ans)

Submission status: Accepted

Solution code:
n,m,q = [int(_) for _ in 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] = [int(_) for _ in input().split()]
  a[i] = a[i]-1 # 初期値を減らす
  b[i] = 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


def dfs(A):
  if len(A) == n: # ここで配列が出揃うので計算して返す
    return score(A)
  if len(A) > 0: # 最初は-1 がないからここで定義してやる
    prev_last = A[-1]
  else:
    prev_last = 1
  result = 0
  for v in range(prev_last,m+1):
    A.append(v)
    result = max(result,dfs(A))
    A.pop()
  return result

print(dfs([]))

Submission status: Accepted

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

#深さ優先探索により各数列を生成する
As=[]
from queue import LifoQueue as lq
S=lq()
S.put([])
while not S.empty():
  a=S.get()
  if len(a)==N:
    As.append(a)
  else:
    if len(a)==0:
      b=1
    else:
      b=a[-1]
    for  i in range(b,M+1):
      S.put(a+[i])

#各数列のスコアを求める
ls_score=[]
for ls in As:
  score=0
  for j in range(Q):
    if ls[ls_rq[j][1]-1]-ls[ls_rq[j][0]-1]==ls_rq[j][2]:
      score+=ls_rq[j][3]
  ls_score.append(score)    
  score=0

#スコアの最大値を求める  
ans=max(ls_score)  
print(ans)

Submission status: Accepted

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

#深さ優先探索により各数列を生成する
As=[]
from queue import LifoQueue as lq
S=lq()
S.put([])
while not S.empty():
  a=S.get()
  if len(a)==N:
    As.append(a)
  else:
    if len(a)==0:
      b=1
    else:
      b=a[-1]
    for  i in range(b,M+1):
      S.put(a+[i])

#各数列のスコアを求める
ls_score=[]
for ls in As:
  score=0
  for j in range(Q):
    if ls[ls_rq[j][1]-1]-ls[ls_rq[j][0]-1]==ls_rq[j][2]:
      score+=ls_rq[j][3]
  ls_score.append(score)    
  score=0

#スコアの最大値を求める  
ans=max(ls_score+[0])  
print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

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

kumi = []
for _ in range(Q):
    tmp = list(map(int, readline().split()))
    kumi.append(tmp)

ans = 0
res = []
def F(l):
    if len(l) == N:
        ans = 0
        for i in range(Q):
            a, b, c, d = kumi[i]
            if l[b-1] - l[a-1] == c:
                ans += d
        return ans
    ans = 0
    start = l[-1] if len(l) else 0
    for i in range(start, M):
        l.append(i)
        ans = max(ans, F(l))
        l.pop()
    return ans
    
ans = F([])
print(ans)

Submission status: Accepted

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

def dfs(n,m):
    adj = {}
    for i in range(1,m+1):
        adj[i] = [j for j in range(i,m+1)]
    
    stack = [[i] for i in range(1,m+1)]
    combs = []
    while stack:
        node = stack.pop()
        if len(node) == n:
            combs.append(node)
        else:
            for child in adj[node[-1]]:
                cand = node+[child]
                stack.append(cand)
    return combs


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,b = a-1, b-1
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)

ans = 0
combs = dfs(N,M)
#combs = cwr(range(1,M+1),N)
# print(combs)
ans = [0]*(len(combs))
for i,comb in enumerate(combs):
    for a,b,c,d in zip(A,B,C,D):
        if comb[b] - comb[a] ==c:
            ans[i] += d
print(max(ans))

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
n,m,q=map(int,input().split())
aa=[]
bb=[]
cc=[]
dd=[]
for i in range(q):
  a,b,c,d=map(int,input().split())
  aa.append(a-1)
  bb.append(b-1)
  cc.append(c)
  dd.append(d)
sumd=[]
#print(list(combinations(range(1,m+1),n)))
for Alis in combinations_with_replacement(range(1,m+1),n):
  
  di=0
  
  for i in range(q):
    if cc[i]==(Alis[bb[i]]-Alis[aa[i]]):
      di+=dd[i]
      
  sumd.append(di)
print(max(sumd))

Submission status: Accepted

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

def combi(use_num_list):
    for i in range(max(use_num_list), M):
        if len(use_num_list) == N:
            combi_list.append(use_num_list[1:] + [i])
            continue
        else:
            combi(use_num_list + [i])

combi(use_num_list)

for cmb in combi_list:
    tmp_ans = 0
    for int_combi in integer_list:
        if cmb[int_combi[1] - 1] - cmb[int_combi[0] - 1] == int_combi[2]:
            tmp_ans += int_combi[3]
    
    ans = max(ans, tmp_ans)
print(ans)

Submission status: Accepted

Solution code:
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())

    def cal(A):
        ans = 0
        for ai, bi, ci, di in zip(a, b, c, d):
            if A[bi-1] - A[ai-1] == ci:
                ans += di
        return ans

    def dfs(A):
        if len(A) == n:
            return cal(A)
        res = 0
        pre = A[-1] if len(A) > 0 else 1
        for i in range(pre, m+1):
            A.append(i)
            res = max(dfs(A), res)
            A.pop()
        return res

    print(dfs([]))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def listup(n, m):
    d = []
    c = [1 for i in range(n)]
    while True:
        d.append(tuple(c))
        if c == [m for i in range(n)]:
            break
        c[n - 1] += 1
        if c[n - 1] > m:
            for i in range(n - 1):
                if c[n - 2 - i] == m:
                    continue
                c[n - i - 2] += 1
                for j in range(i + 1):
                    c[n - i - 1 + j] = c[n - i - 2]
                break
    return d

d = listup(n, m)
dmax = 0
for i in range(len(d)):
    cura = d[i]
    di = 0
    for j in range(q):
        if cura[data[j][1] - 1] - cura[data[j][0] - 1] == data[j][2]:
            di += data[j][3]
    if dmax < di:
        dmax = di

print(dmax)

Submission status: Accepted

Solution code:
N,M,Q = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(Q)]
def dfs(s):
    if len(s) == N:
        return[s]
    result = []
    if s == '':
        num = 0
    else:
        num = int(s[-1])
    for i in range(num,M):
        result.extend(dfs(s+str(i)))
    return result
ans = 0
S = dfs('')
for s in S:
    C = [int(i)+1 for i in s]
    B = 0
    for a,b,c,d in A:
        if C[b-1] - C[a-1] == c:
            B += d
    ans = max(ans,B)
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n, m, q = map(int, readline().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, readline().split())

A = [1]
ans = 0
def dfs():
    if len(A) == n + 1:
        acc = 0
        for i in range(q):
            if A[b[i]] - A[a[i]] == c[i]:
                acc += d[i]
        global ans
        ans = max(ans, acc)
        return
    A.append(A[-1])
    while A[-1] <= m:
        dfs()
        A[-1] += 1
    A.pop()

dfs()
print(ans)

Submission status: Accepted

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

def dfs(s):
    if len(s) == n:
        global ans
        count = 0
        for a,b,c,d in abcd:
            a -= 1
            b -= 1
            if s[b] - s[a] == c:
                count += d
        ans = max(ans, count)
        return
    for i in range(s[-1], m+1):
        dfs(s + [i])
for i in range(1,m+1):
    dfs([i])
print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

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

kumi = []
for _ in range(Q):
    tmp = list(map(int, readline().split()))
    kumi.append(tmp)

ans = 0
res = []
def F(l):
    if len(l) == N:
        ans = 0
        for i in range(Q):
            a, b, c, d = kumi[i]
            if l[b-1] - l[a-1] == c:
                ans += d
        yield ans
        return
    start = l[-1] if len(l) else 0
    for i in range(start, M):
        l.append(i)
        yield from F(l)
        l.pop()
    
ans = max(F([]))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
N,M,Q=map(int,input().split())
G=[]
for _ in range(Q):
  A,B,C,D=map(int,input().split())
  G.append([A,B,C,D])

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

Submission status: Accepted

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

max_score = 0


def dfs(start, end, depth, numbers):
    if depth == N:
        global max_score
        for n in range(start, end + 1):
            A = (*numbers, n)
            score = 0
            for a, b, c, d in records:
                if A[b - 1] - A[a - 1] == c:
                    score += d
            max_score = max(max_score, score)
    else:
        for n in range(start, end + 1):
            dfs(start=n, end=end, depth=depth + 1, numbers=(*numbers, n))


dfs(start=1, end=M, depth=1, numbers=())
print(max_score)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

max_score = 0

for A in combinations_with_replacement(range(1, M + 1), r=N):
    score = 0
    for a, b, c, d in records:
        if A[b - 1] - A[a - 1] == c:
            score += d
    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(' '))
records = [tuple(map(int, input().split(' '))) for _ in range(Q)]

max_score = 0

for A in combinations_with_replacement(range(1, M + 1), r=N):
    A = sorted(A)
    score = 0
    for a, b, c, d in records:
        if A[b - 1] - A[a - 1] == c:
            score += d
    max_score = max(max_score, score)

print(max_score)

Submission status: Accepted

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

def dfs(A=[1]): # A:1 origin
    if n+1 <= len(A):
        return sum(d if A[b]-A[a]==c else 0 for a,b,c,d in abcd)
    A.append(A[-1])
    ret = 0
    while A[-1] <= m:
        ret = max(ret, dfs(A))
        A[-1] += 1
    A.pop()
    return ret

ans = dfs()
print(ans)

Submission status: Accepted

Solution code:
from itertools import *
n, m, q = map(int, input().split())

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

for i in range(q):
    a_temp, b_temp, c_temp, d_temp = map(int, input().split())
    a.append(a_temp)
    b.append(b_temp)
    c.append(c_temp)
    d.append(d_temp)

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

ans = 0
ans_i = 0

for A_i in A:
    for i in range(q):
        if A_i[b[i] - 1] - A_i[a[i] - 1] == c[i]:
            ans_i += d[i]

    ans = max(ans, ans_i)
    ans_i = 0

print(ans)

Submission status: Accepted

Solution code:
def dfs(A, d):
    ans = 0
    if d == N:
        for a, b, c, d in ABCD:
            if A[b] - A[a] == c:
                ans += d
        return ans
    if A:
        s = A[-1]
    else:
        s = 1
    for i in range(s, M+1):
        ans = max(ans, dfs(A+[i], d+1))
    return ans

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

print(dfs([], 0))

Submission status: Accepted

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


def plus():
    l[n - 1] += 1
    while m + 1 in l:
        a = l.index(m + 1)
        l[a - 1] += 1
        for i in range(a, n):
            l[i] = l[a - 1]


ans = 0
while l[0] <= m:
    score = 0
    for i in range(q):
        if l[abcd[i][1] - 1] - l[abcd[i][0] - 1] == abcd[i][2]:
            score += abcd[i][3]
    if ans < score:
        ans = score
    plus()

print(ans)

Submission status: Accepted

Solution code:
n,m,q = map(int,input().split())
abcd = [[] for j in range(q)]
for i in range(q):
    abcd[i] = list(map(int,input().split()))
l = [1]*n
l[n-1]=m
def plus():
    l[n-2] += 1
    while m+1 in l:
        a = l.index(m+1)
        l[a-1]+=1
        for i in range(a,n-1):
            l[i] = l[a-1]

ans=0
while l[0]<=m:
    score = 0
    for i in range(q):
        if l[abcd[i][1]-1]-l[abcd[i][0]-1]==abcd[i][2]:
            score += abcd[i][3]
    if ans < score:
        ans = score
    plus()


print(ans)

Submission status: Accepted

Solution code:
n,m,q = map(int,input().split())
abcd = [[*map(int,input().split())] for _ in range(q)]
from itertools import *
ans = 0
for A in combinations_with_replacement(range(1, m+1), n): # nHr
    now = sum(d if A[b-1] - A[a-1] == c else 0 for a,b,c,d in abcd)
    ans = max(ans, now)
print(ans)

Submission status: Accepted

Solution code:
n,m,q = map(int,input().split())
abcd = [[*map(int,input().split())] for _ in range(q)]
from itertools import *
ans = 0
for A in combinations_with_replacement(range(1, m+1), n): # nHr
    now = 0
    for a,b,c,d in abcd:
        if A[b-1] - A[a-1] == c: now += d
    ans = max(ans, now)
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 solve(N, M, Q, ABCD):
    As = []
    dfs(As, [1], N)
    answer = 0
    for A in As:
        point = 0
        for a, b, c, d in ABCD:
            point += d if A[b] - A[a] == c else 0
        answer = max(answer, point)
    print(answer)


def dfs(As, A, N):
    if len(A) == N+1:
        As.append(A)
        return
    a = A[-1]
    for b in range(a, M+1):
        A_ = A[:]
        A_.append(b)
        dfs(As, A_, N)
    
solve(N, M, Q, ABCD)

Submission status: Accepted

Solution code:
N, M, Q = map(int,input().split())
a_d = [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):
                                        A = [i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]
                                        tmp = 0
                                        for a,b,c,d in a_d:
                                            if A[b-1]-A[a-1] == c:
                                                tmp += d
                                        ans = max(ans,tmp)
print(ans)

Submission status: Accepted

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

res = 0
for product in itertools.combinations_with_replacement(range(1, M+1), N):
  S = 0
  for a,b,c,d in abcd:
    if product[b-1] - product[a-1] == c:
      S += d
  res = max(res, S)

print(res)

Submission status: Accepted

Solution code:
n,m,q = map(int,input().split())
ab = [0]*q
for i in range(q):
    ab[i] = list(map(int,input().split()))
import itertools
data = list(range(m))
r = n
c = list(itertools.combinations_with_replacement(data, r))
ans = 0
for L in c:
    m = 0
    for i in range(q):
        if L[ab[i][1]-1] - L[ab[i][0]-1] == ab[i][2]:
            m += ab[i][3]
    ans = max(ans,m)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

def cal(x):
    rr = 0
    for i in range(Q):
        a,b,c,d = query[i]
        if x[b] - x[a] == c:
            rr += d
    return rr

n,m,Q = inpl()
q = deque()
q.append([1])
query = []
for _ in range(Q):
    query.append(inpl())
res = 0
while q:
    now = q.popleft()
    if len(now) == n+1:
        res = max(res, cal(now))
        continue
    for i in range(now[-1],m+1):
        tmp = now + [i]
        q.append(tmp)
print(res)

Submission status: Accepted

Solution code:
# 全探索の気持ちが芽生える なにを全探索する？
# Qだと2^50なので無理になる、
# Nをしたいが10^10では？と無理になる
# と思いきや条件からA[i-1]<=A[i]なのでだいぶ減りそうとなる
# 計算量の見積もりがぜんぜんできないがたぶんいけるとなる
from collections import deque
n, m, q = map(int, input().split())
queries = []
for _ in range(q):
    queries.append(tuple(map(int, input().split())))

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

ans = 0


def calc(arr):
    ret = 0
    for a, b, c, d in queries:
        if arr[b - 1] - arr[a - 1] == c:
            ret += d
    return ret


while len(queue):
    nex_queue = deque()
    for qq in queue:
        if len(qq) == n:
            ans = max(ans, calc(qq))
        else:
            for i in range(qq[-1], m + 1):
                nex_qq = qq[:]
                nex_qq.append(i)
                nex_queue.append(nex_qq)
    queue = nex_queue

print(ans)

Submission status: Accepted

Solution code:
# 全探索の気持ちが芽生える なにを全探索する？
# Qだと2^50なので無理になる、
# Nをしたいが10^10では？と無理になる
# と思いきや条件からA[i-1]<=A[i]なのでだいぶ減りそうとなる
# 計算量の見積もりがぜんぜんできないがたぶんいけるとなる
from collections import deque
n, m, q = map(int, input().split())
queries = []
for _ in range(q):
    queries.append(tuple(map(int, input().split())))

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

ans = 0


def calc(arr):
    ret = 0
    for a, b, c, d in queries:
        if arr[b - 1] - arr[a - 1] == c:
            ret += d
    return ret


while len(queue):
    qq = queue.popleft()
    if len(qq) == n:
        ans = max(ans, calc(qq))
    else:
        for i in range(qq[-1], m + 1):
            nex_qq = qq[:]
            nex_qq.append(i)
            queue.append(nex_qq)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

n, m, q = map(int, input().split())
INPUT = [list(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 INPUT :
        a -= 1; b -= 1
        if A[b] - A[a] == c:
            temp += d
    ans = max(ans, temp)
print(ans)

Submission status: Accepted

Solution code:
def next_array(array):#辞書式に次の配列を与える関数
  s = -1
  for x in array[::-1]:
    if x < M:
      break
    else:
      s -= 1
    #Mより小さい最後の項を取得
  
  if s >= -N:
    array[s] += 1#その項を１増やす
    if s < -1:
      for i in range(s+1,0):#以降の項を全て同じ値に
        array[i] = array[s]

  return array
 
def score(array, rules):#点数計算
  scr = 0
  for rule in rules:
    if (array[rule[1]-1] - array[rule[0]-1] == rule[2]):
      scr += rule[3]
      
  return scr
 
# input
N, M, Q = map(int, input().split())
rules = []
 
for i in range(Q):
  a, b, c, d = map(int, input().split())
  rules.append([a, b, c, d])
  
array = [1] * N
max_scr = 0
 
while True:
  max_scr = max(max_scr, score(array,rules)) 
  if array[0] == M:#全探索完了
    break 
  array = next_array(array)#次の配列へ
    
print(max_scr)

Submission status: Accepted

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

sequence = [1 for i in range(n)]

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

score = 0
maximum = 0
while sum(sequence) <= n*m:
    for quar in quartet:
        if sequence[quar[1]-1] - sequence[quar[0]-1] == quar[2]:
            score += quar[3]
    
    if maximum < score:
        maximum = score
    
    score = 0
    
    if m in sequence:
        t = sequence.index(m)
        sequence[t-1] += 1
        for i in range(t, n):
            sequence[i] = sequence[t-1]
    else:
        sequence[-1] += 1

print(maximum)

Submission status: Accepted

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

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

def dfs(arr, i):
  global ans
  if len(arr)==n:
    ans=max(ans,calc(arr))
    return
  for j in range(i,m+1):
    arr.append(j)
    dfs(arr, j)
    arr.pop()
dfs([], 1)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as cwr
N,M,Q=map(int,input().split())
A=[]
B=[]
C=[]
D=[]
for _ in range(Q):
    inp=list(map(int,input().split()))
    A.append(inp[0])
    B.append(inp[1])
    C.append(inp[2])
    D.append(inp[3])

all=cwr(range(1,M+1),N)

max_d=0

for tmp in all:
    tmp_d=0
    for i in range(Q):
        if tmp[B[i]-1] - tmp[A[i]-1] == C[i]:
            tmp_d += D[i]
    if max_d < tmp_d:
            max_d = tmp_d
    
print(max_d)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
N, M, Q = map(int, input().split())
A = []
B = []
C = []
D = []
ans = 0
for i in range(Q):
    a, b, c, d = map(int, input().split())
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)

def dfs(n):
    if len(n) == N+1:
        global ans
        tmp = 0
        for i in range(Q):
            if n[B[i]] - n[A[i]] == C[i]:
                tmp += D[i]
        ans = max(ans, tmp)
    else:
        for i in range(n[-1], M+1):
            tmp2 = n[:]
            tmp2.append(i)
            dfs(tmp2)
dfs([1])
print(ans)