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 sys
sys.setrecursionlimit(1000000)

def f(i, j, t):
    global ans
    if j == n:
        c = 0
        for ss in s:
            if t[ss[1] - 1] - t[ss[0] - 1] == ss[2]:
                c += ss[3]
        ans = max(ans, c)
        return
    for k in range(i, m + 1):
        t[j] = k
        f(k, j + 1, t)

n, m, q = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(q)]
t = [1] * n
ans = 0
f(1, 0, t)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

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

for q in range(Q):
  array=list(map(int,input().split()))
  a.append(array[0])
  b.append(array[1])
  c.append(array[2])
  d.append(array[3])

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

MAX=[]

for al in all:
  sum=0
  for q in range(Q):
    if al[b[q]-1]-al[a[q]-1]== c[q]:
      sum += d[q]
  MAX.append(sum)
  
print(max(MAX))

Submission status: Accepted

Solution code:
# やっぱり全探索で大丈夫． その文字列を作る方法がDFSになっております
# まぁどっちでも同じか？なんかこういうときはDFSを使う決まりでもあんのかなぁ
N,M,Q=map(int,input().split())
A=[] # ミュータブルオブジェクトでこれやっちゃうとあかん
B=[]
C=[]
D=[]
for _ in range(Q):
    a,b,c,d=map(int,input().split())
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)

# 再帰で呼び出せばいいらしいんだけど．．．
# 再帰で呼び出して，条件を満たすような文字列を作るように私用．
# 現在作っている文字列のながさがNになった時点でリストにappendするようにする
# dfsで再帰的に文字を返すのではないのがみそか
A_lis=[]
def dfs(s):
    global A_lis
    if len(s)==N:
        A_lis.append(s)
        return None
    last = s[-1]
    for i in range(last,M+1):
        new=s+[i]
        dfs(new)
for a in range(1,M+1):
    dfs([a])
max_score=0
for a in A_lis:
    score=0
    for i in range(Q):
        if a[B[i]-1]-a[A[i]-1]==C[i]:
            score+=D[i]
    max_score=max(max_score,score)
print(max_score)

Submission status: Accepted

Solution code:
import itertools
N, M, Q = map(int, input().split(" "))
abcd = []
for i in range(Q):
    abcd.append(list(map(int, input().split(" "))))
A = list(itertools.combinations_with_replacement(range(1, M + 1), N))
#print(A)
ans = 0            
for a in A:
    score = 0
    for i in abcd:
        if a[i[1] - 1] == a[i[0] - 1] + i[2]:
            score += i[3]
    ans = max(ans, score)
print(ans)

Submission status: Accepted

Solution code:
import sys
from copy import deepcopy
sys.setrecursionlimit(10**7)


def dfs(now):
    global ans
    if len(now) == N:
        tmp_ans = 0
        for a, b, c, d in query:
            a -= 1
            b -= 1
            if now[b] - now[a] == c:
                tmp_ans += d
        ans = max(tmp_ans, ans)
    else:
        for i in range(now[-1], M+1):
            tmp = deepcopy(now)
            tmp.append(i)
            dfs(tmp)


N, M, Q = map(int, input().split())  # N個の数列, 上限M, Q個のクエリ
query = [list(map(int, input().split())) for _ in range(Q)]

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

Submission status: Accepted

Solution code:
import itertools
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

ans=0
for seq in itertools.combinations_with_replacement(range(M),N):
    tmp=0
    for i in range(Q):
        if seq[b[i]]-seq[a[i]]==c[i]:
            tmp+=d[i]
    ans=max(ans,tmp)

print(ans)

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 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 sys
import copy
sys.setrecursionlimit(10**7)


def dfs(now):
    global ans
    if len(now) == N:
        tmp_ans = 0
        for a, b, c, d in query:
            a -= 1
            b -= 1
            if now[b] - now[a] == c:
                tmp_ans += d
        ans = max(tmp_ans, ans)
    else:
        for i in range(now[-1], M+1):
            tmp = copy.deepcopy(now)
            tmp.append(i)
            dfs(tmp)


N, M, Q = map(int, input().split())  # N個の数列, 上限M, Q個のクエリ
query = [list(map(int, input().split())) for _ in range(Q)]

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

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

def generate_arr(target):
    if len(target) == N:
        tmp = 0
        for item in arr:
            if target[item[1]-1] - target[item[0]-1] == item[2]:
                tmp += item[3]
            ans.add(tmp)
        return
    for i in range(target[-1],M+1):
        next_target = target.copy()
        next_target.append(i)
        generate_arr(next_target)
for i in range(1,M+1):
    generate_arr([i])
print(max(ans))

Submission status: Accepted

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

def point(hai):
    hai.reverse()
    point = 0
    for i in range(Q):
        if hai[li[i][1]-1] - hai[li[i][0]-1] == li[i][2]:
            point += li[i][3]

    return point


def tansa(hai):
    global maxnum
    if len(hai) == 0:
        maxnum2 = M
    else:
        maxnum2 = hai[-1]
    for i in range(1, maxnum2+1):
        haicpy = copy.copy(hai)
        hai.append(i)
        if len(hai) == N:
            num = point(copy.copy(hai))
            if maxnum < num:
                maxnum = num
        else:
            tansa(copy.copy(hai))
        hai = haicpy


maxnum = 0
hai = []
tansa(hai)
print(maxnum)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)


def dfs(now):
    global ans
    if len(now) == N:
        tmp_ans = 0
        for a, b, c, d in query:
            a -= 1
            b -= 1
            if now[b] - now[a] == c:
                tmp_ans += d
        ans = max(tmp_ans, ans)
    else:
        for i in range(now[-1], M+1):
            tmp = now.copy()
            tmp.append(i)
            dfs(tmp)


N, M, Q = map(int, input().split())  # N個の数列, 上限M, Q個のクエリ
query = [list(map(int, input().split())) for _ in range(Q)]

A = [1]
ans = 0
dfs(A)
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)]

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

ans = 0
for A in itertools.combinations_with_replacement([i+1 for i in range(M)],N):
    A = list(A)
    A.sort()
    ans = max(ans,func(A))

print(ans)

Submission status: Accepted

Solution code:


def main():
    N, M, Q = [int(x) for x in input().split()]
    queries = [[int(x) for x in input().split()] for _ in range(Q)]

    ans = float("-inf")

    def dfs(A: list):
        nonlocal ans
        if len(A) == N:
            s = sum(d for a, b, c, d in queries if A[b-1]-A[a-1] == c)
            ans = max(ans, s)
        else:
            lo = 1 if not A else A[-1]
            for i in range(lo, M+1):
                A.append(i)
                dfs(A)
                A.pop()
    dfs([])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import itertools

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

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
N, M, Q = map(int, input().split())
A = []
B = []
C = []
D = []
ans = 0
def dfs(l):
    if len(l) == N+1:
        global ans
        now = 0
        for i in range(Q):
            if(l[B[i]] - l[A[i]] == C[i]):
                now += D[i]
        ans = max(ans, now)
    else:
        tmp = l[:]
        tmp.append(l[-1])
        while tmp[-1] <= M:
            dfs(tmp)
            tmp[-1] += 1

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)

dfs([1])
print(ans)

Submission status: Accepted

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

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


results = []
def f(x, A, depth=0):
    if depth == n:
        # print(A, "---------" if A == [1, 3, 4] else '')
        score = 0
        for a, b, c, d in query:
            # print(A[b], A[a], A[b] - A[a], c, ":", d)
            if A[b] - A[a] == c:
                score += d
        results.append(score)
        return

    for i in range(1, x + 1):
        A[n - depth - 1] = i
        f(i, A, depth + 1)

f(m, [0] * n)
print(max(results))

Submission status: Accepted

Solution code:
N,M,Q = map(int,input().split())
query = [None] * Q
for i in range(Q):
  query[i] = list(map(int,input().split()))
  
def calc(arr,query):
  res = 0
  for a,b,c,d in query:
    if arr[b-1] - arr[a-1] == c:
      res += d
  return res
  
ans = 0
import itertools
for arr in itertools.combinations_with_replacement(range(1,M+1),N):
  val = calc(arr,query)
  if ans < val:
    ans = val
print(ans)

Submission status: Accepted

Solution code:
import itertools as it
n,m,q=map(int, input().split())
x=[list(map(int, input().split())) for i in range(q)]
a,ans = [],0
for i in range(1,m+1):
    a.append(i)
b = list(it.combinations_with_replacement(a, n))
for i in range(0,len(b)):
    c = 0
    for j in range(0,len(x)):
        d,e,f = x[j][0],x[j][1],x[j][2]
        if b[i][e-1] - b[i][d-1] == f:
            c += x[j][3]
    if c > ans:
        ans = c
print(ans)

Submission status: Accepted

Solution code:
import itertools

n, m , q = (int(x) for x in input().split())
list=[]
for i in range(q):
    a, b, c, d = (int(x) for x in input().split())
    list.append((a,b,c,d))
ans = 0
for i in itertools.combinations_with_replacement(range(1,m+1),n):
    score = 0
    for j in range(q):
        if i[list[j][1]-1]-i[list[j][0]-1]==list[j][2]:
            score+=list[j][3]
    if ans<score:
        ans=score
print(ans)

Submission status: Accepted

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

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

def dfs(s):
    last_s = int(s[-1])
    next_s = [str(x) for x in range(last_s, m + 1)]
    for i in next_s:
        t = s[:]
        t.append(i)
        if len(t) == n + 1:
            all_pattern.append(t[1:])
        else:
            dfs(t)
dfs(start)
ans = 0
for pattern in all_pattern:
    res = 0
    for i in range(q):
        a, b, c, d = abcd[i]
        if int(pattern[b - 1]) - int(pattern[a - 1]) == c:
            res += d
    ans = max(ans, res)
#print(all_pattern)
print(ans)

Submission status: Accepted

Solution code:
# C - Many Requirements
from collections import deque
from typing import Tuple

N: int
M: int
conditions: Tuple[Tuple[int, int, int, int]]


def dfs():
    queue = deque([[1]])
    highest = 0
    while queue:
        seq = queue.popleft()
        if len(seq) == N + 1:
            highest = max(
                highest, sum(d for a, b, c, d in conditions if seq[b] - seq[a] == c)
            )
        else:
            for i in range(seq[-1], M + 1):
                queue.append(seq + [i])
    return highest


def main():
    global N, M, conditions
    N, M, Q, *ABCD = map(int, open(0).read().split())
    conditions = tuple(zip(*[iter(ABCD)] * 4))
    print(dfs())


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N, M, Q = map(int, readline().rstrip().split())
    P = [tuple(map(int, readline().rstrip().split())) for _ in range(Q)]
    ans = 0    
    for pair in combinations_with_replacement([i for i in range(1, M+1)], N):
        score = 0
        for a, b, c, d in P:
            if pair[b-1] - pair[a-1] == c:
                score += d
        ans = max(ans, score)
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)


def dfs(num):
    global N, ans, M
    n = len(num)
    if n == N:
        cnt = 0
        for a, b, c, d in con:
            a -= 1; b -= 1
            if num[b] - num[a] == c:
                cnt += d
        ans = max(ans, cnt)
    else:
        e = 1 if n == 0 else num[-1]
        for i in range(e, M + 1):
            dfs((*num, i))


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

ans = 0
dfs(tuple())

print(ans)

Submission status: Accepted

Solution code:
# ABC165 C

import itertools

def main():
    n, m, q = map(int, input().split())
    List = []
    for i in range(q):
        a, b, c, d = map(int, input().split())
        List.append([a, b, c, d])
    
    max_total = 0

    for A in list(itertools.combinations_with_replacement(range(1, m+1),n)):
        total = 0
        for abcd in List:
            if A[abcd[1]-1] - A[abcd[0]-1] == abcd[2]:
                total += abcd[3]
        #print(total)
        if total >= max_total:
            max_total = total
    
    print(max_total)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
def LI():return list(map(int,input().split()))
n,m,q=LI()
abcd=[]
for _ in range(q):
  a,b,c,d=LI()
  a-=1
  b-=1  
  abcd.append((a,b,c,d))
As=itertools.combinations_with_replacement(range(m),n)
ans=0
for A in As:
  cnt=0
  for a,b,c,d in abcd:
    if A[b]-A[a]==c:cnt+=d
  ans=max(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

nax = 0
for x in l:
    score = 0
    for i in range(Q):
        if int(x[b[i]-1]) - int(x[a[i]-1]) == c[i]:
            score += d[i]
    nax = max(nax,score)

print(nax)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as c 
n, m, q = map(int, input().split()) 
arr = [] 
for i in range(q): 
    l = [*map(int, input().split())] 
    arr.append(l) 
res = 0
for g in c(list(range(1, m+1)), n): 
    f = 0 
    for h in arr:
        if g[h[1]-1] - g[h[0]-1] == h[2]: 
            f += h[3]
    res = max(res, f) 
print(res)

Submission status: Accepted

Solution code:
import itertools
li=[]
n,m,q=map(int,input().split())#n:Aの長さ m:A[n]の最大値 q=(a,b,c,d)の組の数
ans=0
ansl=[0]
for cnt in range(q):
    a,b,c,d=map(int,input().split())
    li.append([a,b,c,d])
for A in itertools.combinations_with_replacement(range(1,m+1),n):#重複組み合わせmHn
    for i in range(q):
        if li[i][2]==A[li[i][1]-1]-A[li[i][0]-1]:
            ans+=li[i][3]
    ansl.append(ans)
    ans=0
print(max(ansl))

Submission status: Accepted

Solution code:
import copy
N, M, Q = map(int, input().split())
A = []
B = []
C = []
D = []
ans = 0
def dfs(l):
    if len(l) == N+1:
        global ans
        now = 0
        for i in range(Q):
            if(l[B[i]] - l[A[i]] == C[i]):
                now += D[i]
        ans = max(ans, now)
    else:
        tmp = copy.copy(l)
        tmp.append(l[-1])
        while tmp[-1] <= M:
            dfs(tmp)
            tmp[-1] += 1

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)

dfs([1])
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import combinations_with_replacement

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M, Q = MAP()
ABCD = []
for i in range(Q):
    a, b, c, d = MAP()
    ABCD.append((a-1, b-1, c, d))

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

Submission status: Accepted

Solution code:
n, m, q = map(int, input().split())
l = [[int(i) for i in input().split()] for _ in range(q)]
m -= 1
mx = 0


def main(x, y, A, c):
  global mx
  if x == n and y == m:
    pts = 0
    for i in l:
      if int(A[i[1]-1])-int(A[i[0]-1]) == i[2]:
        pts += i[3]
    mx = max(mx, pts)
    return
  if x < n:
    nA = A+str(c)
    main(x+1, y, nA, c)
  if y < m:
    nc = c+1
    main(x, y+1, A, nc)


main(0, 0, "", 0)
print(mx)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

def dfs(A):
    # 再代入のため、グローバル宣言
    global ans
    
    # N桁なら計算
    if len(A) == N:
        score = 0
        for a, b, c, d in buff:
            if A[b-1] - A[a-1] == c:
                score += d
        ans = max(ans, score)
        return
    
    A.append(A[-1])
    # 再帰
    while A[-1] <= M:
        # コピーを渡す
        dfs(A[:])
        A[-1] += 1


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

ans = 0
dfs([1])

print(ans)

Submission status: Accepted

Solution code:
import copy

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

ans = 0

def dfs(al):
    global ans
    if len(al) == n:
        test = 0
        for i in range(q):
            if al[b[i]-1] - al[a[i]-1] == c[i]:
                test += d[i]
        ans = max(ans, test)
        return
    
    al.append(al[-1])
    i = len(al)
    while True:
        if al[i-1] > m:
            break
        dfs(copy.deepcopy(al))
        al[i-1] += 1

dfs([1])
print(ans)

Submission status: Accepted

Solution code:
n, m, q = map(int, input().split())
l = [[int(i) for i in input().split()] for _ in range(q)]
m -= 1
mx = 0


def gen_A(x, y, A, c):
  global mx
  if x == n and y == m:
    pts = 0
    for i in l:
      if int(A[i[1]-1])-int(A[i[0]-1]) == i[2]:
        pts += i[3]
    mx = max(mx, pts)
    return
  if x < n:
    nA = A+str(c)
    gen_A(x+1, y, nA, c)
  if y < m:
    nc = c+1
    gen_A(x, y+1, A, nc)


gen_A(0, 0, "", 0)
print(mx)

Submission status: Accepted

Solution code:
from itertools import*
(n,m,_),*t=[[*map(int,t.split())]for t in open(0)]
print(max(sum(d*(z[b-1]-z[a-1]==c)for a,b,c,d in t)for z in combinations_with_replacement(range(m),n)))

Submission status: Accepted

Solution code:
from pprint import pprint
import itertools


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

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



a_lists = list(itertools.combinations_with_replacement(range(m), n))

#print(a_lists)

dmax = 0

for a_mini in a_lists:
    dtemp = 0
    for ql_mini in ql:
        if a_mini[ql_mini[1]-1] - a_mini[ql_mini[0]-1] == ql_mini[2]:
            dtemp += ql_mini[3]
        else:
            pass
    if dtemp >= dmax:
        dmax = dtemp

print(dmax)

Submission status: Accepted

Solution code:
# C - Many Requirements
from typing import List, Tuple

N: int
M: int
conditions: Tuple[Tuple[int, int, int, int]]


def rec(seq: List[int]):
    if len(seq) == N + 1:
        return sum(d for a, b, c, d in conditions if seq[b] - seq[a] == c)
    return max(rec(seq + [i]) for i in range(seq[-1], M + 1))


def main():
    global N, M, conditions
    N, M, Q, *ABCD = map(int, open(0).read().split())
    conditions = tuple(zip(*[iter(ABCD)] * 4))
    print(rec([1]))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

l = set(range(1,m+1))
h = itertools.combinations_with_replacement(l, n)

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

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin


def input():
    return stdin.readline().strip()


def main():
    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())
        a[i] -= 1
        b[i] -= 1

    ans = 0

    def dfs(seq):
        nonlocal ans
        if len(seq) == N:
            score = 0
            for i in range(Q):
                if seq[b[i]] - seq[a[i]] == c[i]:
                    score += d[i]
            ans = max(ans, score)
            return

        score = 0
        for n in range(seq[-1], M + 1):
            seq.append(n)
            dfs(seq)
            seq.pop()

    dfs([1])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

result = 0
 
kumi = itertools.combinations_with_replacement(range(1, m+1), n)

for kumi in kumi:
    temp = 0
    for j in range(q):
        if kumi[num_list[j][1]-1] - kumi[num_list[j][0]-1] == num_list[j][2]:
            temp += num_list[j][3]
            result = max(temp,result)

print(result)

Submission status: Accepted

Solution code:
from collections import Counter
import sys
sys.setrecursionlimit(200000)


def read():
    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))
    return N, M, Q, ABCD


def iter_combinations(a, r):

    q = []

    def _dfs(a, r, m=[]):
        if r == 0:
            q.append(m)
        else:
            for i in range(len(a)):
                _dfs(a[i:], r-1, m + [a[i]])
    
    _dfs(list(a), r)
    return q
        

def solve(N, M, Q, ABCD):
    smax = 0
    for x in iter_combinations(range(1, M+1), N):
        sd = 0
        for a, b, c, d in ABCD:
            if x[b-1] - x[a-1] == c:
                sd += d
        smax = max(smax, sd)
    return smax


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("{}".format(outputs))

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

As = combinations_with_replacement(range(1, M+1), N)

ans = 0
for A in As:
    now = 0
    for q in q_list:
        if A[q[1]] - A[q[0]] == q[2]:
            now += q[3]
    ans = max(ans, now)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            a,b,c=(inp+[1])[:3]
            org_inp.append(inp)
        else:
            index=0
            a,b,c=(ls[i]+[1])[:3]
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

class Tree:
    def __init__(self,inp_size=None,init=True):
        if init:
            self.stdin(inp_size)
        return

    def stdin(self,inp_size=None):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1)
        return
    
    def listin(self,ls):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls)
        return

    def __str__(self):
        return  str(self.edges)

    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append((-1,x))
        v=[None]*self.size
        v[x]=root_v
        et=[]
        while q:
            cb,ce=q.pop()
            et.append(ce)
            for nb,d in self.edges[ce]:
                if v[nb]==None:
                    q.append((nb,ce))
                    q.append((ce,nb))
                    v[nb]=func(v[ce],nb,d)
        vid=[[-1,-1]for i in range(self.size)]
        for i,j in enumerate(et):
            if vid[j][0]==-1:
                vid[j][0]=i
            else:
                vid[j][1]=i
        return v,et,vid
    
    def LCA_init(self,depth,et):
        self.st=SegTree(self.size*2-1,func=min,ide=inf)
        for i,j in enumerate(et):
            self.st.update(i,j)
        self.LCA_init_stat==True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            depth,et,vid=self.EulerTour(root)
            self.LCA_init(depth,et)
        return self.st.query(x,y+1)

show_flg=False
show_flg=True

p=[]
def pat(n,m,ls):
    if ls:
        M=ls[-1]
    else:
        M=1

    if n==0:
        p.append(ls[:])
        return
    
    for i in range(M,m+1):
        pat(n-1,m,ls[:]+[i])

ans=0
z=[]
N,M,q=LI()
pat(N,M,[])
for i in range(q):
    a,b,c,d=LI()
    z+=[(a,b,c,d)]

for y in p:
    
    tmp=0
    for a,b,c,d in z:
        if y[b-1]-y[a-1]==c:
            tmp+=d
    if ans<tmp:
        ans=tmp
        rt=y[:]

print(ans)

Submission status: Accepted

Solution code:
n, m , q = map(int, input().split())
 
l = []
for i in range(q):
  a,b,c,d = map(int, input().split())
  l.append((a,b,c,d))
max_score = 0
comb = [[1]]
while len(comb) > 0:
  seed = comb.pop()
  if len(seed) == n:
    score = 0
    for j in l:
      if seed[j[1]-1]-seed[j[0]-1]==j[2]:
      
        score += j[3]
    if score > max_score:
      max_score = score
  else:
    for k in range(seed[-1], m+1):
      s = seed[:]
      s.append(k)
      comb.append(s)
print(max_score)