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:
from itertools import combinations_with_replacement

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

A_max = 0

for conbi in combinations_with_replacement(range(1,m+1), n):
    tmp = 0

    for A_list in A_lists:
        if conbi[A_list[1]-1] - conbi[A_list[0]-1] == A_list[2]:
            tmp += A_list[3]

    A_max = max(A_max, tmp)

print(A_max)

Submission status: Accepted

Solution code:
import itertools

N, M, Q = [int(i) for i in input().split()]
ABCD = [list(map(int, input().split())) for i in range(Q)]
score = 0
for A in itertools.combinations_with_replacement(range(1, M+1), N):
    tmp = 0
    for a, b, c, d in ABCD:
        if A[b-1] - A[a-1] == c:
            tmp += d
    score = max(score, tmp)
print(score)

Submission status: Accepted

Solution code:
def solver(x):
    s = 0
    for y in Query:
        if x[y[1]-1]-x[y[0]-1] ==y[2]:
            s+=y[3]
           
    return s
N,M,Q = map(int,input().split())
Query = []
for x in range(Q):
    a,b,c,d = map(int,input().split())
    Query.append([a,b,c,d])
ans = 0
for x1 in range(M):
    for x2 in range(x1,M):
        for x3 in range(x2,M):
            for x4 in range(x3,M):
                for x5 in range(x4,M) :
                    for x6 in range(x5,M):
                        for x7 in range(x6,M):
                            for x8 in range(x7,M):
                                for x9 in range(x8,M):
                                    for xa in range(x9,M):
                                        t = solver([x1,x2,x3,x4,x5,x6,x7,x8,x9,xa])
                                        if ans <t:
                                            ans =t
print(ans)

Submission status: Accepted

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

def f(l):

    if len(l) == n:
        combos.append(l)
        return

    start = 1 if len(l) == 0 else l[-1]

    for i in range(start, m + 1):
        f(l + [i])

f([])

for combo in combos:
    tmp = 0
    for pair in pairs:
        if combo[pair[1]-1] - combo[pair[0]-1] == pair[2]:
            tmp += pair[3]
    ans = max(tmp, ans)

print(ans)

Submission status: Accepted

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

def dfs(A):
    global ans
    if len(A) == n + 1:
        point = 0
        for i in range(q):
            if A[lst[i][1]] - A[lst[i][0]] == lst[i][2]:
                point += lst[i][3]
                ans = max(ans, point)
        return
    A.append(A[-1])
    while A[-1] <= m:
        dfs(A[:])
        A[-1] += 1

dfs([1])

print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
N, M, Q = map(int, input().split())
a, b, c, d = [], [], [], []
for i in range(Q):
    tmp = list(map(int, input().split()))
    a.append(tmp[0])
    b.append(tmp[1])
    c.append(tmp[2])
    d.append(tmp[3])

ans = 0
def dfs(A):
    global ans
    if len(A) == N + 1:
        now = 0
        for i in range(Q):
            if A[b[i]] - A[a[i]] == c[i]:
                now += d[i]
        ans = max(ans, now)
        return

    A.append(A[-1])
    while A[-1] <= M:
        dfs(deepcopy(A))
        A[-1] += 1

dfs([1])
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
n, m, q = map(int, input().split())
L = []
for _ in range(q):
    a, b, c, d = map(int, input().split())
    a -= 1
    b -= 1
    L.append((a, b, c, d))

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

N = list(range(1, n+m))
P = list(combinations(N, n))
ans = 0
for c in P:
  A = [c[i]-i for i in range(n)]
  g = calc(A)
  if g > ans:
    ans = g
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 A in combinations_with_replacement(range(1,M+1), N):
    pts = 0
    for a, b, c, d in abcd:
        if A[b-1] - A[a-1] == c:
            pts += d
    ans = max(ans, pts)

print(ans)

Submission status: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

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

def dfs(i,s):
    if i==10:
        return pt(s)
    mx = -1
    s1 = s[-1]
    for j in range(s1,m+1):
        s.append(j)
        v = dfs(i+1,s)
        mx = max(mx,v)
        s.pop()
    return mx

n,m,q = inm()
a = []
b = []
c = []
d = []
for i in range(q):
    aa,bb,cc,dd = inm()
    a.append(aa)
    b.append(bb)
    c.append(cc)
    d.append(dd)
s = [1]
print(dfs(0,s))

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

n=0
m=0
ans=-inf
l=[]

def dfs(s):
  global n
  global m
  global ans
  global l

  if len(s)==n:
    _ans=0
    for a,b,c,d in l:
      a-=1
      b-=1
      if s[b]-s[a]==c:
        _ans+=d
    ans=max(ans,_ans)

  if len(s)!=n:
    x=s[-1]
    for i in range(x,m+1):
      dfs(s+[i])

def main():
  global n
  global m
  global ans
  global l

  n,m,q=LI()
  l=[LI() for _ in range(q)]

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

  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
import itertools

N, M, Q = map(int, input().split())
As = list(itertools.combinations_with_replacement(range(1, M + 1), N))

ans = [0]*len(As)
for _ in range(Q):
    a, b, c, d = map(int, input().split())
    for i, A in enumerate(As):
        if A[b-1]-A[a-1] == c:
            ans[i] += d

print(max(ans))

Submission status: Accepted

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

def gen(N, M, st=1):
    if N == 0:
        yield []
    else:
        for i in range(st, M + 1):
            for r in gen(N - 1, M, i):
                yield [i] + r

def calc(xs, abcd):
    return sum((xs[b - 1] - xs[a - 1] == c) * d for a, b, c, d in abcd)

result = 0

for x in gen(N, M):
    r = calc(x, ABCD)
    result = max(result, r)

print(result)

Submission status: Accepted

Solution code:
n, m, q = list(map(lambda x: int(x), input().split(' ')))

e = []

for i in range(q):
  s = list(map(lambda x: int(x), input().split(' ')))
  e.append(s)

def helper(l, tmp, n, all):
  if len(tmp) == n:
    r = tmp.copy()
    all.append(r)
    return

  for i, v in enumerate(l):
    tmp.append(v)
    helper(l[i:], tmp, n, all)
    tmp.pop()

candidates = []
helper(list(range(1, m+1)), [], n, candidates)

max_val = 0

for c in candidates:
  sum = 0

  for j in e:
    if c[j[1] - 1] - c[j[0] - 1] == j[2]:
      sum += j[3]

  max_val = max(max_val, sum)

print(max_val)

Submission status: Accepted

Solution code:
n,m,q = map(int,input().split())
g = []
for i in range(q):
  a,b,c,d = map(int,input().split())
  g.append([a,b,c,d])
MAX = 0
def check(x):
  ten = 0
  for i in range(q):
    a,b,c,d = g[i]
    if x[b-1]-x[a-1] == c:
      ten += d
  return ten
def dfs(s):
  global MAX
  if len(s) == n:
    MAX = max(check(s),MAX)
    return
  for i in range(s[-1],m+1):
    s.append(i)
    dfs(s)
    s.pop()
for i in range(1,m+1):
  dfs([i])
print(MAX)

Submission status: Accepted

Solution code:
n, m, q = map(int, input().split())
req = []
[req.append(tuple(map(int, input().split()))) for _ in range(q)]
a = [0 for _ in range(n)]

def check():
    res = 0
    for i in range(q):
        ra, rb, rc, rd = req[i]
        if a[rb - 1] - a[ra - 1] == rc:
            res += rd
    return res

def set_a(idx: int, au: int):
    ans = 0
    for i in range(au, m + 1):
        a[idx] = i
        if idx + 1 < n:
            ans = max(set_a(idx + 1, i), ans)
        else:
            ans = max(check(), ans)
    return ans

print(set_a(0, 1))

Submission status: Accepted

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

Sd = [list(map(int, input().split())) for i in range(Q)]
A = [1] * N

def point(ablock,A):
    p = 0
    for qlist in ablock:
        if(A[qlist[1]-1] - A[qlist[0]-1] == qlist[2]):
            p += qlist[3]
    return p

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

ans = 0
for c in comb:
    sug = point(Sd, c)
    if ans < sug:
        ans = sug

print(ans)

Submission status: Accepted

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

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

from itertools import permutations, combinations,combinations_with_replacement,product
AA=range(1,M+1)
CM = list(combinations_with_replacement(AA,N))
#print(CM)
wa = 0
A = [0]*N
dammy=[]
for i in range(len(CM)):
    A = CM[i]
    for j in range(Q):
        #print(abcd[2][j])
        if (A[abcd[j][1]-1] - A[abcd[j][0]-1]) == abcd[j][2]:
            wa+=abcd[j][3]
    dammy.append(wa)
    wa =0

print(max(dammy))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys,os
from collections import defaultdict, deque
from math import ceil, floor
if sys.version_info[1] >= 5:
    from math import gcd
else:
    from fractions import gcd
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    MOD = 10**9+7

    N,M,Q = LMIIS()
    A = [0]*N

    query = [0]*Q
    for i in range(Q):
        a,b,c,d = LMIIS()
        query[i] = (a,b,c,d)

    from itertools import combinations_with_replacement
    max_score = 0
    for T in combinations_with_replacement(range(1,M+1),N):
        tmp_score = 0
        for a,b,c,d in query:
            if T[b-1] - T[a-1] == c:
                tmp_score += d
        max_score = max(max_score, tmp_score)
    print(max_score)







if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

s = ['1']
s_list = []

def dfs(s):
    last_s = int(s[-1])
    for i in range(last_s, m + 1):
        t = s[:]
        t.append(str(i))
        if len(t) == n + 1:
            s_list.append(t[1:])
        else:
            dfs(t)

dfs(s)

ans = 0

for s in s_list:
    res = 0
    for i in range(q):
        a, b, c, d = abcd[i]
        if int(s[b - 1]) - int(s[a - 1]) == c:
            res += d
    ans = max(res, ans)

print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
import itertools
N,M,Q=map(int,input().split())
T=[]

H=0
for y in range(Q):
    a,b,c,d=map(int,input().split())
    t=(a,b,c,d)
    T.append(t)
A=[x+1 for x in range(M)]
B=list(itertools.combinations_with_replacement(A,N))
C=len(B)
for z in range(C):
    E=B[z]
    G=0
    for l in range(Q):
        F=T[l]
        g=F[0]-1
        h=F[1]-1
        i=F[2]
        if E[h]-E[g]==i:
            G+=F[3]
    if G>=H:
        H=G
print(H)

Submission status: Accepted

Solution code:
import itertools

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

for i in itertools.combinations_with_replacement(range(1, M + 1), N):
    total = 0
    for j in range(Q):
        if i[abcd[j][1] - 1] - i[abcd[j][0] - 1] == abcd[j][2]:
            total += abcd[j][3]
    ans = max(ans, total)

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

A_li = tuple(itertools.combinations_with_replacement(range(m), n))

score = 0

for A in A_li:
  tmp = 0
  for nums in li:
    ai =  nums[0]-1
    bi = nums[1]-1
    ci = nums[2]
    di = nums[3]
    
    if A[bi] - A[ai] == ci:
      tmp += di
  score = max(score, tmp)
  
print(score)

Submission status: Accepted

Solution code:
import itertools

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

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

ans = [0] * len(As)
for _ in range(q):
  a, b, c, d = map(int, input().split())
  for i, A in enumerate(As):
    if A[b-1] - A[a-1] == c:
      ans[i] += d

print(max(ans))

Submission status: Accepted

Solution code:
import itertools

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

q = []

for i in range(1, m+1):
    q.append(i)

ret = 0

for item in itertools.combinations_with_replacement(q, n):
    score = 0
    for t_item in t_list:
        if item[t_item[1]-1] - item[t_item[0]-1] == t_item[2]:
            score += t_item[3]
    ret = max(ret, score)

print(ret)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def examA():
    K = I()
    A, B = LI()
    for i in range(A,B+1):
        if i%K==0:
            print("OK")
            return
    print("NG")
    return

def examB():
    X = I()
    now = 100
    ans = 0
    while(now<X):
        ans += 1
        now += now//100
    print(ans)
    return

def examC():
    N, M, Q = LI()
    A = [LI()for _ in range(Q)]
    A.sort()
    dp = [[0]*M for _ in range(N)]
    for i in range(Q):
        a, b, c, d = A[i]
        a -= 1; b -= 1
        for j in range(M):
            dp[b][j] = max(dp[b][j],0)


    ans = 0
    print(ans)
    return

# 反省して下さい。
def examC2():
    N, M, Q = LI()
    A = [LI()for _ in range(Q)]
    C = list(itertools.combinations_with_replacement(range(1, M + 1), N))
    #rint(C)
    ans = 0
    for L in C:
        cur = 0
        for a, b, c, d in A:
            if (L[b-1]-L[a-1]==c):
                cur += d
        ans = max(cur,ans)
    print(ans)
    return

def examD():
    A, B, N = LI()
    if N>=B-1:
        ans = (A*(B-1))//B
    else:
        ans = (A*N)//B
    print(ans)
    return

def examE():
    N, M = LI()
    ans = []
    if N%2==1:
        for i in range(N // 2):
            ans.append((i + 1, N - i))
    else:
        flag = False
        for i in range(N // 2):
            if N-i-(i+1)<=N//2:
                flag = True
            if flag:
                ans.append((i+1,N-i-1))
            else:
                ans.append((i + 1, N - i))
    #print(ans)
    for v in ans[:M]:
        print(" ".join(map(str,v)))
    return

def examF():
    N = I()
    A = LI()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        u, v = LI()
        u -= 1; v -= 1
        V[u].append(v)
        V[v].append(u)
    dp = [-1]*N
    dp[0] = 1
    LIS = deque()
    LIS.append(A[0])
    def dfs(s):
        #print(LIS)
        for i in V[s]:
            if dp[i]!=-1:
                continue
            flag = []
            if A[i] > LIS[-1]:
                LIS.append(A[i])
                flag = False
            else:
                flag = [bisect.bisect_left(LIS, A[i]),LIS[bisect.bisect_left(LIS, A[i])]]
                LIS[flag[0]] = A[i]
            dp[i] = len(LIS)
            dfs(i)
            #print(flag)
            if not flag:
                LIS.pop()
            else:
                LIS[flag[0]] = flag[1]
        return
    dfs(0)
    ans = dp
    for v in ans:
        print(v)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examC2()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

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

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

ans=0

for c in itertools.combinations_with_replacement(range(1, m + 1), n):
    a=0
    for j in ql:
        if c[j[1]-1] - c[j[0]-1] == j[2]:
            a += j[3]
    if ans < a:
        ans = a
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

res = 0

for A in combinations_with_replacement(range(1, M + 1), N):
    point = 0
    for a, b, c, d in Q:
        if A[b - 1] - A[a - 1] == c:
            point += d
    res = max(point, res)

print(res)

Submission status: Accepted

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


def inpl():
    return list(map(int, input().split()))


def backtrack(n, ml, mh, tmp=[]):
    if n == 0:
        yield tmp
        return

    for i in range(ml, mh + 1):
        yield from backtrack(n - 1, i, mh, tmp + [i])


def main():
    def count(ca):
        return sum(d for a, b, c, d in abcd if ca[b - 1] - ca[a - 1] == c)
    N, M, Q = inpl()
    abcd = [inpl() for _ in range(Q)]
    print(max(count(c) for c in backtrack(N, 1, M)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m, q = 0, 0, 0
Q = []

def main():
    global n, m, q
    n, m, q = map(int, input().split())
    for _ in range(q):
        a, b, c, d = map(int, input().split())
        a, b = a - 1, b - 1
        Q.append([a, b, c, d])
    ans = solve()
    print(ans)

def solve():
    ans = 0
    for i in range(1, m + 1):
        ans = max(ans, dfs([i], 0))
    return ans

def dfs(A, ans):
    #print('dfs({}, {}, {})'.format(A, n, m))
    if len(A) == n:
        tmp = sum([Q[i][3] for i in range(q) if A[Q[i][1]] - A[Q[i][0]] == Q[i][2]])
        #print('A:{} score:{}'.format(A, tmp))

        return max(ans, tmp)

    A.append(A[-1])
    while A[-1] <= m:
        ans = max(ans, dfs(A, ans))
        A[-1] += 1
    A.pop()
    
    return ans

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as cwr

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

combs = cwr(range(1, m+1), n)
ans = 0
for comb in combs:
  cand = 0
  for a, b, c, d in scores:
    if comb[b-1] - comb[a-1] == c:
      cand += d
  ans = max(ans, cand)
print(ans)

Submission status: Accepted

Solution code:
import itertools
n, m, q = map(int, input().split())
abcd = [tuple(map(int, input().split())) for _ in range(q)]
Max = 0
for A in itertools.combinations_with_replacement(range(1, m + 1), n):
    #score = sum([d for a, b, c, d in abcd if C[b - 1] - C[a - 1] == c])
    score = 0
    for ai, bi, ci, di in abcd:
        if A[bi - 1] - A[ai - 1] == ci:
            score += di
    Max = max(Max, score)
    #print(C)
print(Max)

Submission status: Accepted

Solution code:
n,m,q = map(int,input().split())
kouho = [int(i) for i in range(1,m+1)]
kouho_list = [1]*(n+1)
Input = []
for i in range(q):
    tmp = [int(i) for i in input().split()]
    Input.append(tmp)

def rec(N,Min):
    global ans
    if N==1:
        ans =0
    if N==n:
        score = 0
        for i in range(q):
            a,b,c,d = Input[i][0],Input[i][1],Input[i][2],Input[i][3]
            if kouho_list[b-1]-kouho_list[a-1] == c:
                score += d
        ans = max(ans,score)
        return 0
    for i in range(Min,m+1):
        kouho_list[N] = i
        rec(N+1,i)
rec(1,1)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

from itertools import combinations_with_replacement
def main():
    N, M, Q = map(int, input().split())
    Abcd = [list(map(int,input().split())) for i in range(Q)]
    L = list(combinations_with_replacement(range(1,M+1), N))
    ret = 0

    for l in L:
        pt = 0
        for abcd in Abcd:
            if l[abcd[1]-1] - l[abcd[0]-1] == abcd[2]:
                pt += abcd[3]
        ret = max(ret, pt)
    print(ret)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N, M, Q = rl()
A, B, C, D = [], [], [], []
for i in range(Q):
	a, b, c, d = rl()
	A.append(a-1)
	B.append(b-1)
	C.append(c)
	D.append(d)

def check(nums):
	for i in range(len(nums)-1):
		if nums[i] > nums[i+1]:
			return False
	return True

def f(nums):
	s = 0
	for i in range(Q):
		if nums[B[i]]-nums[A[i]] == C[i]:
			s += D[i]
	return s

nums = [0] * N
def myiter(M, N, i=0):
	if i == N:
		yield nums
		return
	prev = 1
	if i > 0:
		prev = nums[i-1]
	for j in range(prev,M+1):
		nums[i] = j
		for y in myiter(M, N, i+1):
			yield y


ans = 0
for nums in myiter(M, N):
	if check(nums):
		n = f(nums)
		ans = max(ans, n)
print(ans)

Submission status: Accepted

Solution code:
N,M,Q = map(int,input().split())
lis = []
i = 0
ai,bi,dist,poin = [],[],[],[]
while True:
    try:
        lis.append(list(map(int,input().split())))
        ai.append(lis[i][0])
        bi.append(lis[i][1])
        dist.append(lis[i][2])
        poin.append(lis[i][3])
        i+=1

    except:
        break;
        #または、quit(),os.exit()をして止める。
#print(bi)
        
def point(num):
  tok = 0
  for i in range(Q):
    #print('A(='+str(num[ai[i]-1])+') - B(='+str(num[bi[i]-1])+') = dist(='+str(dist[i]))
    if(num[bi[i]-1] - num[ai[i]-1] == dist[i]):
      tok += poin[i]
  return tok

#per = [M**i for i in range(1,N+1)].sort()

def UpdateA(num):
  NewA = num
  flag = 0
  i = N-1
  while(flag == 0 and i >= 0):
    NewA[i] += 1
    if(NewA[i] > M):
      i -= 1
      continue
    else:
      j=i+1
      while(j<N):
        NewA[j] = NewA[j-1]
        j+=1
      flag = 1
  #print('NewA - '+str(NewA))
  return NewA
  
maxi = 0
A = [1 for i in range(N)]
while(1):
  thisp = point(A)
  #print('this p = '+str(thisp))
  if(thisp > maxi):
    maxi = thisp
    #print('maxi - '+str(maxi))
    if(maxi == sum(poin)):
      break
  A = UpdateA(A)
  if(sum(A) > N*M):
    break

print(maxi)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
n, m, q = map(int, input().split())
A = combinations_with_replacement(range(m), n)
L = []

for _ in range(q):
    L.append(list(map(int, input().split())))

r = 0
for a in A:
    t = 0
    for l in L:
        if a[l[1] - 1] - a[l[0] - 1] == l[2]:
            t += l[3]
    if t > r:
        r = t
print(r)