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 collections import deque

n, m, q = map(int,input().split())
q_list = []
point_list = []

for i in range(q):
    temp_list = list(map(int,input().split()))
    q_list.append(temp_list)

que = deque()
que.append([1,[]])
ans = 0
temp_list = []

while len(que) != 0:
    temp = que.pop()
    if len(temp[1]) != n:
        temp_list = []
        for i in range(temp[0], m+1):
            for j in temp[1]:
                temp_list.append(j)
            temp_list.append(i)
            que.append([i, temp_list])
            temp_list = []
    else:
        point = 0
        for q in q_list:
            if temp[1][q[1]-1] - temp[1][q[0]-1] == q[2]:
                point += q[3]
        if ans < point:
            ans = point

print(ans)

Submission status: Accepted

Solution code:
nmq = [int(x) for x in input().split()]

n = nmq[0]
m = nmq[1]
q = nmq[2]

lis = []

for i in range(0,q):
    lis.append([int(x) for x in input().split()])

def check(ar):
    total = 0
    for thing in lis:
        if ar[thing[1]] - ar[thing[0]] == thing[2]:
            total = total + thing[3]
    return total

def solve(pre,count):
    count = int(count)
    if count == n:
        return(check(pre))
    else:
        maxx = 0
        for i in range(pre[count],m+1):
            temp = solve(pre + [i], count+1)
            if temp > maxx:
                maxx = temp
        return(maxx)
    
print(solve([1],0))

Submission status: Accepted

Solution code:
import sys
sys.stdin.readline

def dfs(dmax, now):
    if len(now) == N:
        P.append(now)
        return
    for n in range(dmax, M+1):
        dfs(n, now+[n])

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

dfs(1, [])
ans = 0
for A in P:
    score = 0
    for a, b, c, d in ABCD:
        if A[b-1] - A[a-1] == c:
            score += d
    ans = max(ans, score)

print(ans)

Submission status: Accepted

Solution code:
N,M,Q=map(int,input().split())
S=[]
for i in range(Q):
    S.append(list(map(int,input().split())))
try_lis=[]
def dfs(A):
    if len(A)==N:
        try_lis.append(A[::1])
        return   
    for v in range(1,M+1):
        if v>=A[-1]:
            A.append(v)
            dfs(A)
            A.pop()
dfs([1])
total=0
for one_case in try_lis:
    tmp=0
    for j in S:
        if one_case[j[1]-1]-one_case[j[0]-1]==j[2]:
            tmp+=j[3]
    total=max(total,tmp)
print(total)

Submission status: Accepted

Solution code:
N,M,Q=map(int,input().split())
S=[]
for i in range(Q):
    S.append(list(map(int,input().split())))
try_lis=[]
def dfs(A):
    if len(A)==N:
        try_lis.append(A[::1])
        return   
    for v in range(1,M+1):
        if v>=A[-1]:
            A.append(v)
            dfs(A)
            A.pop()
dfs([1])
total=0
for one_case in try_lis:
    tmp=0
    for j in S:
        if one_case[j[1]-1]-one_case[j[0]-1]==j[2]:
            tmp+=j[3]

    total=max(total,tmp)

print(total)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(1000000) 
ans = 0
def main():
    N, M, Q = map(int, readline().split())
    query = []
    for _ in range(Q):
        a, b, c, d = map(int, readline().split())
        a -= 1
        b -= 1
        query.append((a, b, c, d))

    def slv(A):    
        s = 0
        for a, b, c, d in query:
            if A[b]-A[a] == c:
                s += d
        return s
    #数列Aを構築
    #数列Aを構築できたら計算処理
    from collections import deque 
    A = deque()
    def dfs(p):
        global ans
        if p == N:
            s = 0
            for a, b, c, d in query:
                if A[b]-A[a] == c:
                    s += d
            ans = max(s, ans)
            return
        if len(A) == 0:
            k = 1
        else:
            k = A[p-1]
        for i in range(k, M+1):
            A.append(i)
            dfs(p+1)
            A.pop()
    dfs(0)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
abcd_list = [list(map(int, input().split())) for _ in range(Q)]
Alist = []
def dfs(array):
    if len(array) == N:
        Alist.append(array)
    else:
        if not array:
            for i in range(1, M+1):
                dfs(array[:] + [i])
        else:
            for i in range(array[-1], M+1):
                dfs(array[:] + [i])
dfs([])
ans = 0
for A in Alist:
    res = 0
    for a, b, c, d in abcd_list:
        if A[b-1] - A[a-1] == c:
            res += d
    ans = max(ans, res)
print(ans)

Submission status: Accepted

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

from itertools import combinations_with_replacement

ans=0
for a in combinations_with_replacement(range(1, m+1,), n):
    d=0
    for i in range(q):
        if a[abcd[i][1]-1]-a[abcd[i][0]-1]==abcd[i][2]:
            d+=abcd[i][3]
    ans=max(ans,d)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as c

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

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

for i in c(range(1,m+1),n):
    s=0
    for j in Q:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            s+=j[3]
    a=max(a,s)
print(a)

Submission status: Accepted

Solution code:
def dfs(seq):
    # 返り値は、すべての数列の得点の最大値 ans です。
    ans = 0
    if len(seq) == n:
        # 数列が完成したので、得点を計算します
        score_ret = 0
        for a, b, c, d in req:
            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,)  # 長さ1のタプル(i,)を連結します
            score = dfs(seq_next)  # seq_nextから派生するすベての数列の中での、得点の最大値が返ってきます
            ans = max(ans, score)  # 最大の得点を更新します
 
    # すべてが終わったので、得点の最大値を返します
    return ans
 
 
n, m, q = list(map(int, input().split()))
# reqは[[a1,b1,c1,d1],[a2,b2,c2,d2]……]が入ったリストのリストです
req = [list(map(int, input().split())) for _ in range(q)]
 
# 最終的に答えが返ってくるようにします。処理はすべてdfsメソッドでやってもらいます。
# リストだとどこかで間違えて値を書き換えそうで怖いので、タプルにしておきます
# 1番目が1の場合以外は考えなくていいので、(1,)だけやります
ans = 0
score = dfs((1,))
ans = max(ans, score)
print(ans)

Submission status: Accepted

Solution code:
def calc(l):
  t=0
  for ai,bi,ci,di in zip(a,b,c,d):
    if l[bi]-l[ai]==ci:
      t+=di
  return t

def dfs(l):
  if len(l)==n:
    return calc(l)
  res=0
  prev_last=0
  if len(l)>0:
    prev_last=l[-1]
  for v in range(prev_last,m):
    l.append(v)
    res=max(res,dfs(l))
    l.pop()
  return res

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

print(dfs([]))

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

result = 0

for x in combinations_with_replacement(range(1, m+1), n):
    t = 0
    for a,b,c,d in abcd:
        if x[b-1] - x[a-1] == c:
            t += d
    result = max(result,t)
print(result)

Submission status: Accepted

Solution code:
nmq=list(map(int, input().split()))
N=nmq[0]
M=nmq[1]
Q=nmq[2]
ablist=[]
for i in range(Q):
    tp=tuple(map(int, input().split()))
    ablist.append(tp)
sumlist=[]
alist=[i for i in range(1,M+1)]
import itertools
case=list(itertools.combinations_with_replacement(alist,N))
for nowcase in case:
    sumd=0
    for i in range(Q):
        if nowcase[ablist[i][1]-1]-nowcase[ablist[i][0]-1]==ablist[i][2]:
            sumd+=ablist[i][3]
    sumlist.append(sumd)
print(max(sumlist))

Submission status: Accepted

Solution code:
def dfs(seq):
    # 返り値は、すべての数列の得点の最大値 ans です。
    ans = 0
    if len(seq) == n:
        # 数列が完成したので、得点を計算します
        score_ret = 0
        for a, b, c, d in req:
            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,)  # 長さ1のタプル(i,)を連結します
            score = dfs(seq_next)  # seq_nextから派生するすベての数列の中での、得点の最大値が返ってきます
            ans = max(ans, score)  # 最大の得点を更新します

    # すべてが終わったので、得点の最大値を返します
    return ans


n, m, q = list(map(int, input().split()))
# reqは[[a1,b1,c1,d1],[a2,b2,c2,d2]……]が入ったリストのリストです
req = [list(map(int, input().split())) for _ in range(q)]

# 最終的に答えが返ってくるようにします。処理はすべてdfsメソッドでやってもらいます。
# リストだとどこかで間違えて値を書き換えそうで怖いので、タプルにしておきます
# 1番目が1の場合以外は考えなくていいので、(1,)だけやります
ans = 0
score = dfs((1,))
ans = max(ans, score)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque


# 数列の点数を計算する関数
def calc(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 = map(int, input().split())
req = [list(map(int, input().split())) for _ in range(q)]

ans = 0

que = deque()

# 数列の1番目、[1]～[m]までキューに追加しますが、
# 実は、この問題は数列の最初が[1]の場合だけを考えても解けます。
for i in range(1, m + 1):
    que.append([i])

while que:
    seq = que.popleft()

    if len(seq) == n:
        # 長さがnになったので、得点を計算します
        score = calc(seq)
        ans = max(ans, score)
    else:
        # 次に追加する数字は、下限が今の数列の一番後ろの数字、上限がmです
        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は[[a1,b1,c1,d1],[a2,b2,c2,d2]……]が入ったリストのリストです
req = [list(map(int, input().split())) for _ in range(q)]

ans = 0
# seqは長さnのタプルです
for seq in comb_rplc(range(1, m + 1), n):
    score = 0
    for a, b, c, d in req:
        # 問題文に書いてある数列のk番目は、インデックスだとk-1になるので注意
        if seq[b - 1] - seq[a - 1] == c:
            score += d
    ans = max(ans, score)

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n, m, q = map(int, input().split())
    abcd = [list(map(int, input().split())) for _ in range(q)]

    arr = []

    def dfs(num, ai):
        if len(ai) == n:
            arr.append(ai)
        elif len(ai) < n:
            for i in range(num, m + 1):
                dfs(i, ai + [i])

    ans = 0

    dfs(1, [])

    for ai in arr:
        score = 0
        for a, b, c, d in abcd:
            if ai[b - 1] - ai[a - 1] == c:
                score += d
        if ans < score:
            ans = score

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

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

dic = {}
for i in range(Q):
  a, b, c, d = map(int, input().split())
  dic[(a-1, b-1, c-1)] = d
ans = 0
for ar in itertools.combinations_with_replacement(range(1, M+1), N):
  D = 0
  for com in dic.keys():
    if ar[com[1]] - ar[com[0]] == com[2]+1:
      D += dic[com]
  if D > ans:
    ans = D
print(ans)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
import heapq

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

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

max_p = 0
for r in res:
    p = 0
    for query in abcds_list:
        a, b, c, d = query
        if r[b-1] - r[a-1] == c:
            p += d
    if p > max_p:
        max_p = p
print(max_p)

Submission status: Accepted

Solution code:

def calc(nums):
    ret = 0
    for a, b, c, d in req:
        if nums[b - 1] - nums[a - 1] == c:
            ret += d
 
    return ret
 
 
n, m, q = list(map(int, input().split()))
req = [list(map(int, input().split())) for _ in range(q)]
 
ans = 0
 
stack = []
 
# [1]～[m]までキューに追加します。実は[1]だけでもいいです。考えてみてください。
for i in range(1, m + 1):
    stack.append([i])
 
while stack:
    seq = stack.pop()
 
    if len(seq) == n:
        score = calc(seq)
        ans = max(ans, score)
    else:
        for i in range(seq[-1], m + 1):
            seq_next = seq + [i]
            stack.append(seq_next)
 
print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import copy
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

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

ans = 0
def dfs(i, numlist):
    if i == N:
        # numlistを元に得点計算
        cnt = 0
        for jud in lista:
            if numlist[jud[1]] - numlist[jud[0]] == jud[2]:
                cnt += jud[3]
        return cnt

    ans = 0
    # もしi = 0なら
    sta = 0
    # もしi != 0なら一個前の数字を参照
    if i > 0:
        sta = numlist[i - 1]
    # 1つ前の数字が1なら1 ~ 10までをdfs
    # 重複組み合わせ
    for j in range(sta, M):
        # 数字を記録
        numlist[i] = j
        ans = max(ans, dfs(i + 1, numlist))
    return ans
print(dfs(0, [0] * N))

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
    
def dfs(A):
    if len(A)==N:
        return score(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

if __name__ == '__main__':
    nmq = input()
    nmq = nmq.split()
    n = int(nmq[0])
    m = int(nmq[1])
    q = int(nmq[2])

    abcd = [0]*q
    for i in range(q):
        ele = input()
        ele = ele.split()
        ele = list(map(int,ele))
        abcd[i] = ele

    comb = [i+1 for i in range(m)]

    comb_list = list(itertools.combinations_with_replacement(comb,n))


    max_amount = 0
    for i in range(len(comb_list)):
        amount = 0
        for j in range(q):
            if (comb_list[i][abcd[j][1]-1] - comb_list[i][abcd[j][0]-1]) == abcd[j][2]:
                amount += abcd[j][3]
        max_amount = max(max_amount,amount)

    print(max_amount)

Submission status: Accepted

Solution code:
# Python 3
import sys
import itertools
import numpy as np
 
read = sys.stdin.buffer.read #標準入力から複数行取得するための関数です。 readlines() が結果を行単位で分割してリストで返すのに対して、 read() は結果をそのまま1つの文字列として取得します。
readline = sys.stdin.buffer.readline #標準入力から1行取得するための関数です。
readlines = sys.stdin.buffer.readlines #標準入力から複数行取得するための関数です。戻り値はリストで、入力された文字列が1行ずつ要素として格納されています。

N, M, Q = map(int, readline().split())
 
A = np.array(list(itertools.combinations_with_replacement(range(1, M + 1), N)))
# [[1 1 1]
#  [1 1 2]
#  [1 1 3]
#  [1 1 4]
#  [1 2 2] ...
# NumPy配列

n = len(A)
score = np.zeros(n, np.int32)
m = map(int, read().split())
for a, b, c, d in zip(m, m, m, m):
    cond = A[:, b - 1] - A[:, a - 1] == c # NumPy配列
    score += d * cond
 
print(score.max())

Submission status: Accepted

Solution code:
import sys

def ket(anw,m):
    wk=len(anw)
    while sum(anw)<=wk*m:
        anw[wk-1]+=1
        for i in range(wk-1,-1,-1):
            if anw[i]<m+1:
                return(anw)
            else:
                anw[i-1]+=1
                for j in range(i,wk):
                    anw[j]=anw[i-1]
    anw=[0]*wk
    return(anw)

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

wk = 0
an = [1]*n
anw = [1]*n
ten = tenw = 0
while sum(anw)<=n*m:
    for k in range(q):
        if anw[abcd[k][1]-1]-anw[abcd[k][0]-1]==abcd[k][2]:
            tenw += abcd[k][3]
        else:
            pass
    if ten < tenw:
        ten = tenw
        an = anw.copy()
        tenw = 0
    else:
        tenw = 0

    anw = ket(anw,m)
    if sum(anw) == 0:
        break

if ten == 0:
    print(0)
else:
    print(ten)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000001)

N, M, Q = map(int, input().split())
a = []
b = []
c = []
d = []
for i in range(Q):
    abcd = list(map(int, input().split()))
    a.append(abcd[0])
    b.append(abcd[1])
    c.append(abcd[2])
    d.append(abcd[3])
A_max = 0
A = [1] * N
def DFS():
    global A_max
    d_sum = 0
    for i in range(Q):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            d_sum += d[i]
    A_max = max(A_max, d_sum)
    if A[0] == M:
        return
    elif A[N-1] != M:
        A[N-1] += 1
    else:
        tmp_index = N-1
        while True:
            tmp_index -= 1
            if A[tmp_index] != M:
                A[tmp_index:] = [A[tmp_index] + 1] * len(A[tmp_index:])
                break
    DFS()

DFS()
print(A_max)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def solve(string):
    from itertools import combinations_with_replacement
    n, m, q, *abcd = map(int, string.split())
    ans = 0
    for v in combinations_with_replacement(range(1, m + 1), n):
        ans = max(
            ans,
            sum(d if v[b - 1] - v[a - 1] == c else 0 for a, b, c, d in zip(*[iter(abcd)] * 4)))
    return str(ans)


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
def solve(string):
    from itertools import combinations_with_replacement
    n, m, q, *abcd = map(int, string.split())
    ans = 0
    for v in combinations_with_replacement(range(1, m + 1), n):
        v = sorted(list(v))
        ans = max(
            ans,
            sum(d if v[b - 1] - v[a - 1] == c else 0 for a, b, c, d in zip(*[iter(abcd)] * 4)))
    return str(ans)


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

n, m, q = map(int, (input().split()))
lst = [list(map(int, input().split())) for i in range(q)]
ptn = combinations_with_replacement(range(1, m + 1), n)
ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
import itertools
N, M, Q    = [ int(i) for i in input().strip().split(' ')]

data = []
for n in range(Q):
    data.append([ int(i) for i in input().strip().split(' ')])

x = [ 1+i for i in range(M)]
max_total = 0
for A in itertools.combinations_with_replacement(x, N):
    total = 0
    for a,b,c,d in data:
        if A[b-1] - A[a-1] == c:
            total += d
    
    if max_total < total:
        max_total = total
print(max_total)

Submission status: Accepted

Solution code:
import itertools

def abcd(n):
  for _ in range(n):
    a,b,c,d = map(int,input().split())
    yield a,b,c,d

def main():
  N,M,Q = map(int,input().split())
  num = list(range(1,M+1))
  X = list(abcd(Q))
  for v in itertools.combinations_with_replacement(num, N):
    ans = 0
    for a,b,c,d in X:
      A,B = v[a-1],v[b-1]
      if B-A == c:
        ans += d
    yield ans

print(max(main()))

Submission status: Accepted

Solution code:
import itertools
n,m,q=map(int,input().split())
a=[]
b=[]
c=[]
d=[]
for _ in range(q):
    li=list(map(int,input().split()))
    a.append(li[0])
    b.append(li[1])
    c.append(li[2])
    d.append(li[3])

#print(a,b,c,d)

h=list(itertools.combinations_with_replacement(range(1,m+1),n))
#print(h)
#print(len(h))

max_score=0
for j in range(len(h)):
    score=0
    for i in range(q):
        if h[j][b[i]-1]-h[j][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())
Arr = [list((map(int, input().split()))) for i in range(Q)]
Alist = list(itertools.combinations_with_replacement(range(1, M+1), N))
result = 0

for A in Alist:
    score = 0
    for q in range(Q):
        if A[Arr[q][1]-1] - A[Arr[q][0]-1] == Arr[q][2]:
            score += Arr[q][3]
    result = max(result, score)

print(result)

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
#N: 正整数列の長さ, M:正整数列の最大値, Q: 4つの整数の組みの数

a_l = [0]*Q
b_l = [0]*Q
c_l = [0]*Q
d_l = [0]*Q
for i in range(Q):
    a_l[i], b_l[i], c_l[i], d_l[i] = map(int, input().split())

def calc_score(now):
    score = 0
    for a, b, c, d in zip(a_l, b_l, c_l, d_l):
        a -= 1
        b -= 1
        if c == (now[b]-now[a]):
            score += d

    return score

def dfs(now, n, num): #nowはこれから生成するもの
    if n == 0:
        score_list.append(calc_score(now))
    else:
        for i in range(num, M+1):
            dfs(now+[i], n-1, i)

score_list = []
dfs([], N, 1)
print(max(score_list))

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement


def main():
    n, m, q = map(int, input().split())
    abcd = []
    for i in range(q):
        tmp = list(map(int, input().split()))
        tmp[0] -= 1
        tmp[1] -= 1
        abcd.append(tmp)
    # abcd.sort(key=lambda x: x[3], reverse=True)

    ans = 0
    for comb in combinations_with_replacement(range(1, m+1), n):
        # print(comb)
        tmp = 0
        for a, b, c, d in abcd:
            if comb[b]-comb[a] == c:
                tmp += d
        if ans < tmp:
            ans = tmp
    print(ans)

    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
#N: 正整数列の長さ, M:正整数列の最大値, Q: 4つの整数の組みの数

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

def dfs(now, n, num): #nowはこれから生成するもの
    if n == 0:
        make_group.append(now)
    else:
        for i in range(num, M+1):
            dfs(now+[i], n-1, i)

make_group = []
dfs([], N, 1)
ans = 0
for group in make_group:
    tmp = 0
    for q in Q_li:
        a = q[0] - 1
        b = q[1] - 1
        if q[2] == (group[b] - group[a]):
            tmp += q[3]
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

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

al=[0]*q
bl=[0]*q
cl=[0]*q
dl=[0]*q

for i in range(q):
    al[i],bl[i],cl[i],dl[i]=map(int,input().split())

def score_calc(seq):
    res=0
    for a,b,c,d in zip(al,bl,cl,dl):
        if seq[b-1]-seq[a-1]==c:
            res+=d
    return res
score_list=[]
def dfs(seq):
    if len(seq)==n:
        score_list.append(score_calc(seq))
        return 
    lastone=seq[-1] if len(seq)>0 else 1
    for v in range(lastone,m+1):
        seq.append(v)
        dfs(seq)
        seq.pop()

dfs([])
print(max(score_list))

Submission status: Accepted

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

a = [0] * Q
b = [0] * Q
c = [0] * Q
d = [0] * Q
A = [0] * (N + 1)

ans = 0

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



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

A[0] = 1
dfs(0)

print(ans)

Submission status: Accepted

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics

sys.setrecursionlimit(10000001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===
def main():
    n, m, q = ns()
    d = [na() for _ in range(q)]

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

    ans = 0
    for c in cmb:
        tmp_ans = 0
        for ai, bi, ci, di in d:
            if c[bi - 1] - c[ai - 1] == ci:
                tmp_ans += di
        ans = max(ans, tmp_ans)

    print(ans)


if __name__ == '__main__':
    main()

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)]
nums = combinations_with_replacement(range(1, m+1), n)
ans = 0

for i in nums:
    tmp = 0
    for j in abcd:
        if i[j[1]-1] - i[j[0]-1] == j[2]:
            tmp += j[3]
    ans = max(ans, tmp)
        
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)]

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

ans = 0
for i in nums:
  t = 0
  for j in abcd:
    s = i[j[1]-1] - i[j[0]-1]
    if s == j[2]:
      t += j[3]
  ans = max(ans, t)
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

a = [0]
b = [0]
c = [0]
d = [0]

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

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

ans = 0
for l in A:
    s = 0
    for i in range(1, Q + 1):
        if l[b[i]-1] - l[a[i]-1] == c[i]:
            s += d[i]
    else:
        if s > ans:
            ans = s

print(ans)

Submission status: Accepted

Solution code:
from collections import deque


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

    return ret


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

ans = 0

que = deque()

# [1]～[m]までキューに追加します。実は[1]だけでもいいです。考えてみてください。
for i in range(1, m + 1):
    que.append([i])

while que:
    seq = que.pop()

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

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

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

print(ans)

Submission status: Accepted

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

from collections import deque

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

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

d = deque([1]*N)

total_max = 0

while True:
    A = list(d)

    total = 0
    
    for i in range(Q):
        if A[abcd[i][1]-1]-A[abcd[i][0]-1] == abcd[i][2]:
            total += abcd[i][3]

    total_max = max(total_max,total)

    cnt = 1

    if A == [M]*N:
        break

    while True:
        ai = d.pop()
        if ai != M:
            for j in range(cnt):
                d.append(ai+1)
            break
        cnt += 1


print(total_max)

Submission status: Accepted

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

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

def dfs(seq):
    if len(seq) == n:
        yield seq
        return
    if not seq:
        _max = 1
    else:
        _max = seq[-1]
    for i in range(_max, m+1):
        new_seq = seq.copy()
        new_seq.append(i)
        yield from dfs(new_seq)

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