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
n, m, q = map(int, input().split())
alis, blis, clis, dlis = [], [], [], []
for _ in range(q):
    a, b, c, d = map(int, input().split())
    alis.append(a)
    blis.append(b)
    clis.append(c)
    dlis.append(d)
sys.setrecursionlimit(10**9)
Alist = [] 
def dfs(A):
    if len(A)==(n+1):
        Alist.append(A)
        return
    for i in range(A[-1], m+1):
        dfs(A+[i])

dfs([1])

ans = 0
for A in Alist:
    score = 0
    for i in range(q):
        if A[blis[i]] - A[alis[i]] == clis[i]:
            score += dlis[i]
    ans = max(ans, score)

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

def saitenn(suuretu):
    global numbers_list
    score = 0
    for numbers in numbers_list:
        a = numbers[0] - 1
        b = numbers[1] - 1
        c = numbers[2]
        d = numbers[3]

        if suuretu[b] - suuretu[a] == c:
            score += d
    return score

for A in itertools.combinations_with_replacement(range(1, m+1), n):
    score = saitenn(A)
    ans = max(ans, score)

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

max_num = 0
for num_lst in itertools.combinations_with_replacement(range(1, m + 1), n):
    count = 0
    for a, b, c, d in lst:
        if num_lst[b - 1] - num_lst[a - 1] == c:
            count += d
    max_num = max(max_num, count)
print(max_num)

Submission status: Accepted

Solution code:
import itertools

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

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

ans = 0
for A in A_list:
    sum = 0
    for a,b,c,d in abcd:
        if A[b-1] - A[a-1] == c:
            sum += d
    ans = max(ans, sum)

print(ans)

Submission status: Accepted

Solution code:
n,m,q = map(int,input().split())
abcd = [list(map(int,input().split())) for _ in range(q)]
ans = 0
for a in range(1,m+1):
  for b in range(a,m+1):
    for c in range(b,m+1):
      for d in range(c,m+1):
        for e in range(d,m+1):
          for f in range(e,m+1):
            for g in range(f,m+1):
              for h in range(g,m+1):
                for i in range(h,m+1):
                  for j in range(i,m+1):
                    lst = [0,a,b,c,d,e,f,g,h,i,j]
                    s = 0
                    for l in range(q):
                      s += abcd[l][3]*(lst[abcd[l][1]]-lst[abcd[l][0]]==abcd[l][2])
                    ans = max(ans, s)
print(ans)

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10**6)
ans = [0]
def dfs(idx, now):
    if idx == n:
        #print(now)
        sumd = 0
        for j in abcd:
            if now[j[1]-1] - now[j[0]-1] == j[2]:
                sumd += j[3]
        ans[0] = max(ans[0], sumd)
        return
    if len(now) > 0:
        start = now[-1]
    else:
        start = 1
    for i in range(start, m+1):
        now.append(i)
        dfs(idx + 1, now)
        now.pop()

dfs(0, [])
print(ans[0])

Submission status: Accepted

Solution code:
import itertools

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

for i in range(Q):
    t = [int(x) for x in input().split()]
    a.append(t[0] - 1)
    b.append(t[1] - 1)
    c.append(t[2])
    d.append(t[3])

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

    ans = max(ans, score)

print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m,q = map(int,input().split())
num = [i for i in range(1,m+1)]
q_list = []
for i in range(q):
  q_list.append(list(map(int,input().split())))

a_cand = list(itertools.combinations_with_replacement(num, n))
count_list = []
for a in a_cand:
    count = 0
    for q in q_list:
      if a[q[1]- 1] - a[q[0] - 1] == q[2]:
        count += q[3]
        
    count_list.append(count)
  
print(max(count_list))

Submission status: Accepted

Solution code:
def dfs(A, M, i):
  if i < 0:
    return
  A[i] += 1
  if A[i] > M:
    dfs(A, M, i-1)
    if i-1 >= 0:
      A[i] = A[i-1]

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

A = [1]*N
ans = 0

for _ in range(100000):
  dsum = 0
  for i in range(Q):
    ai,bi,ci,di = a[i], b[i], c[i], d[i]
    if A[bi-1]-A[ai-1] == ci:
      dsum += di
  ans = max(ans, dsum)

  #終了条件
  if A[0]==M:
    break

  #終了しない場合は次の数字
  dfs(A, M, N-1)

print(ans)

Submission status: Accepted

Solution code:
import itertools
n, m, q = map(int, input().split())
lst = [0] * q
for i in range(q):
    a, b, c, d = map(int, input().split())
    lst[i] = (a, b, c, d)
L = list(itertools.combinations_with_replacement(range(1,m+1), n))
ans = 0 
for l in L:
    point_l = 0
    for rule in lst:
        if l[rule[1]-1]-l[rule[0]-1] == rule[2]:
            point_l += rule[3]
    ans = max(ans,point_l)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
def main():
    n, m, q = map(int, input().split())
    qlist = []
    for _ in range(q):
        qlist.append(tuple(map(int, input().split())))

    nums = [i for i in range(1, m + 1)]
    alist = tuple(combinations_with_replacement(nums, n))

    r = 0
    for al in alist:
        tr = 0
        for eq in qlist:
            eq0 = eq[0] - 1
            eq1 = eq[1] - 1
            eq2 = eq[2]
            eq3 = eq[3]
            if al[eq1] - al[eq0] == eq2:
                tr += eq3
        r = max(r, tr)

    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log
from heapq import heapify, heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from decimal import Decimal
inf = float('inf')
MOD = 1000000007
def INT_(n): return int(n) - 1
def MI(): return map(int, input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n: int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')

n, m, q = MI()
abcd = LLIN(q)

ans = 0
num = [0 for _ in range(10)]
for i0 in range(1, m+1):
    num[0] = i0
    for i1 in range(i0, m+1):
        num[1] = i1
        for i2 in range(i1, m+1):
            num[2] = i2
            for i3 in range(i2, m+1):
                num[3] = i3
                for i4 in range(i3, m+1):
                    num[4] = i4
                    for i5 in range(i4, m+1):
                        num[5] = i5
                        for i6 in range(i5, m+1):
                            num[6] = i6
                            for i7 in range(i6, m+1):
                                num[7] = i7
                                for i8 in range(i7, m+1):
                                    num[8] = i8
                                    for i9 in range(i8, m+1):
                                        num[9] = i9
                                        tmp = 0
                                        for a,b,c,d in abcd:
                                            if num[b-1] - num[a-1] == c:
                                                tmp += d
                                        ans = max(ans, tmp)

print(ans)

Submission status: Accepted

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

def dfs(part_A,i):
    if i == N:
        A.append(part_A)
    else:
        for a in range(part_A[-1],M+1):
            dfs(part_A+[a],i+1)

A=[]
dfs([1],1)
max_score=0
for An in A:
    score = 0
    for q in range(Q):
        if An[b[q]-1]-An[a[q]-1] == c[q]:
            score += d[q]
    max_score = max(score, max_score)

print(max_score)

Submission status: Accepted

Solution code:
n, m, q = map(int, input().split())
abcd = []
A = 0
B = 1
C = 2
D = 3
for i in range(q):
    abcd.append(list(map(int, input().split())))

for i in range(q):
    abcd[i][A] -= 1
    abcd[i][B] -= 1

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]
                                        now = 0
                                        for j in range(q):
                                            if a[abcd[j][B]] - a[abcd[j][A]] == abcd[j][C]:
                                                now += abcd[j][D]
                                        ans = max(ans, now)

print(ans)

Submission status: Accepted

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

A = []
score_list = []

#数列A
for i in range(N):
  A.append(0)

#行列として入力
L = []
l = []
for i in range(Q):
  l = list(map(int, input().split()))
  L.append(l)


#数列を深さ優先探索
def search(x, y):
  if x < 0  or x > N - 1 or y < 0 or y > M - 1:
    return
  A[x] = y + 1
  if x == N - 1:
    sum = 0
    for i in range(Q):
      if A[L[i][1] - 1] - A[L[i][0] - 1] == L[i][2]:
        sum += L[i][3]
    score_list.append(sum)
    
  search(x + 1, y)
  search(x, y + 1)

search(0, 0)
print(max(score_list))

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]
ans = 0
from itertools import combinations_with_replacement
l = [i for i in range(1, M+1)]
lis = list(combinations_with_replacement(l, N))

for l in lis:
    tmp = 0
    for j in range(Q):
        a, b, c, d = abcd[j]
        if l[b-1]-l[a-1]==c:
            tmp+=d
    ans = max(tmp, ans)

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
from itertools import combinations_with_replacement

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

ans=0
for i in combinations_with_replacement(range(1,m+1),n):
    tmp=0
    for j in A:
        a,b,c,d=j
        if i[b-1]-i[a-1]==c: tmp+=d
    ans=max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
n, m, q = 0, 0, 0
ABCD = []
ans = 0


def dfs(A):
    global ans

    if len(A) == n:
        s = 0
        for qi in range(q):
            a, b, c, d = ABCD[qi]
            if A[b - 1] - A[a - 1] == c:
                s += d

        ans = max(s, ans)
        return

    for i in range(A[-1], m + 1):
        AC = A.copy()
        AC.append(i)
        dfs(AC)


def main():
    global n, m, q, ABCD
    n, m, q = [int(e) for e in input().split()]
    ABCD = [[int(e) for e in input().split()] for i in range(q)]

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
n, m, q = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(q)]
# print(lst)
def point(A):
    point = 0
    for i in lst:
        if A[i[1]] - A[i[0]] == i[2]:
            point += i[3]
    return point

def solve(A):
    length = len(A) - 1
    if length == n:
        return point(A)
    o = A[length]
    ans = 0
    for i in range(o, m+1):
        ans = max(ans, solve(A + [i]))
    return ans
print(solve([1]))

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement


def main():
    N, M, Q = map(int, input().split())
    conds = [list(map(int, input().split())) for i in range(Q)]
    combs = combinations_with_replacement([i for i in range(1, M+1)], N)
    ans = 0
    for comb in combs:
        ans_ = 0
        for c in conds:
            if comb[c[1]-1] - comb[c[0]-1] == c[2]:
                ans_ += c[3]
        ans = max(ans, ans_)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

up_lsts = list(itertools.combinations_with_replacement(range(1,m + 1), n))
ans = 0
for up_lst in up_lsts:
    tmp = 0
    for req in lst:
        if up_lst[req[1] - 1] - up_lst[req[0] - 1] == req[2]:
            tmp += req[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)]
values = set(i for i in range(1,M+1))
ans = 0
for A in combinations_with_replacement(values, N):
    cnt = 0
    for a,b,c,d in abcd:
        if A[b-1] - A[a-1] == c:
            cnt += d
    ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
num4 = [[(int(i)) for i in input().split()] for _ in range(Q)]
A = [[i]for i in range(M,0,-1)]
Aseq = []
while len(A)!=0: # 全数列が長さNになるまで続ける
  tmp = A.pop(-1)
  if len(tmp)==N: # 長さNの数列は、リストAseqに追加
    Aseq.append(tmp)
    continue
  for i in range(M, tmp[-1]-1,-1): A.append(tmp + [i])
pmax = 0
for A in Aseq:
  p = 0
  for a,b,c,d in num4:
    if int(A[b-1])-int(A[a-1])==c: p += d
  pmax = max(pmax, p)
print(pmax)

Submission status: Accepted

Solution code:
N,M,Q = map(int,input().split())
ar=[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):

                                        con = 0

                                        arr = [0,i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]

                                        for a,b,c,d in ar:
                                            if arr[b] - arr[a] == c:
                                                con += d

                                        ans=max(ans,con)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M,Q = map(int,input().split())
ABCD = [list(map(int,input().split())) for _ in range (Q)]
import sys
sys.setrecursionlimit(10**9)
Alist = []
def dfs(v):
    if len(v)==N:
        Alist.append(v)
        return 
    for t in range(v[-1],M+1):
        dfs(v+[t])
dfs([1])

ans = 0
for A in Alist:
    res = 0
    for a,b,c,d in ABCD:
        if A[b-1]-A[a-1]==c:
            res += d
    ans = max(ans,res)
print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m,q=map(int, input().split())
S = []
for i in range(q):
    a,b,c,d=map(int, input().split())
    S.append([a,b,c,d])
tl=itertools.combinations_with_replacement(range(1,m+1),n)
ans = 0
for l in tl:
    t = 0
    for a,b,c,d in S:
        if l[b-1]-l[a-1] == c:
            t += d
    ans = max(ans,t)
print(ans)

Submission status: Accepted

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

now=[]
stc=[now[:]]
res=[]

def saiki(x,c,ma,n):
    if c== n:
        #print(now)
        res.append(now[:])
        return
    
    for i in range(x,ma+1):
        now.append(i)
        saiki(i,c+1,ma,n)
        now.pop()

saiki(1,0,m,n)  

max_score=0
for C in res:
    score=0
    for i in range(q):
        if C[P[i][1]-1]-C[P[i][0]-1]==P[i][2]:
            score+=P[i][3]
    max_score=max(score,max_score)

print(max_score)

Submission status: Accepted

Solution code:
import sys
import itertools

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline


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


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


def dfs(i, mx):
    if i == N:
        return calc()

    score = 0
    for x in range(mx, M+1):
        A[i] = x
        s = dfs(i+1, x)
        score = max(s, score)
    return score


A = [0] * N
ans = dfs(0, 1)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

N, M, Q = map(int,input().split())
x = [_ for _ in range(1, M+1)]
y = list(combinations_with_replacement(x, N))
l = [list(map(int, input().split())) for _ in range(Q)]

ans = []
z = 0
for i in range(len(y)):
    for j in range(Q):
        if y[i][l[j][1]-1] - y[i][l[j][0]-1] == l[j][2]:
            z += l[j][3]
        ans.append(z)
    z = 0
print(max(ans))

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import math
#標準出力からの読み込み
input_1 = input()
n = int(input_1.split(" ")[0])
m = int(input_1.split(" ")[1])
q = int(input_1.split(" ")[2])

input_array = []
for i in range(q):
    input_array.append(input())

array = []
for i in range(q):
    array.append(input_array[i].split(" "))

for i in range(q):
    for j in range(4):
        array[i][j] = int(array[i][j])


#判定ロジック
#Aについて総当たりで調べる

#重複組み合わせの全組み合わせを得る関数
#1がN個、0がM-1個と考える
def make_all_combi(m, n, array):
    if n == 0:
        for i in range(m-1):
            array = array + [0]
        return array
    elif m == 1:
        for i in range(n):
            array = array + [1]
        return array
    else:
        array_3 = array + [1]
        array_4 = array + [0]
        tmp_list_a = make_all_combi(m, n-1, array_3)
        tmp_list_b = make_all_combi(m-1, n, array_4)
    return tmp_list_a + tmp_list_b

combi = make_all_combi(m, n, [])

#make_all_combiで得た配列に対して、Aを作成する
def make_a(combi):
    A = []
    for i in range(len(combi)//(m+n-1)):
        list_a = combi[i*(m+n-1):(i+1)*(m+n-1)]
        count = 1
        a_cand = []
        for j in range(len(list_a)):
            if list_a[j] == 0:
                count = count + 1
            else:
                a_cand.append(count)
        A.append(a_cand)
    return A

A = make_a(combi)

score = 0
max_a = []
for i in range(len(A)):
    tmp = 0
    for j in range(q):
        if A[i][array[j][1]-1] - A[i][array[j][0]-1] == array[j][2]:
            tmp = tmp + array[j][3]
    if tmp > score:
        score = tmp
        max_a = A

print(score)

Submission status: Accepted

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

from collections import deque
ans = 0
def main():
    N, M, Q = map(int, readline().split())
    query = []
    for _ in range(Q):
        a, b, c, d = map(int, readline().split())
        query.append((a, b, c, d))
    

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

    A = deque()
    def dfs():
        global ans
        n = len(A)
        if n == N:
            ans = max(getScore(A), ans)
        else:
            if n == 0:
                k = 1
            else:
                k = A[-1]
            for i in range(k, M+1):
                A.append(i)
                dfs()
                A.pop()
    dfs()
    print(ans)          
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M,Q=map(int,input().split())
terms=[list(map(int,input().split())) for i in range(Q)]
def dfs(nums,length,min_lim):
    ans=0
    if length==N:
        ans_2=0
        for a,b,c,d in terms:
            if nums[b-1]-nums[a-1]==c:
                ans_2+=d
        return ans_2
    else:
        for i in range(min_lim,M+1):
            new_nums=nums+[i]
            ans_2=dfs(new_nums,length+1,i)
            ans=max(ans,ans_2)
    return ans
print(dfs([],0,1))

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

a = range(1,M+1)
arr = np.asarray(list(itertools.combinations_with_replacement(a,N))) #重複組み合わせ
#print(arr)

sc = np.zeros(arr.shape[0],dtype=int)
#print(sc)

for i in range(Q):
  abcd = list(map(int, input().split()))
  f = (arr[:,abcd[1]-1]-arr[:,abcd[0]-1])==abcd[2]
  sc += abcd[3]*f 
#
print(sc.max())

Submission status: Accepted

Solution code:
import sys
import itertools
import numpy as np
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N, M, Q = map(int, readline().split())
 
A = np.array(list(itertools.combinations_with_replacement(range(1, M + 1), N)))
 
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
    score += d * cond
 
print(score.max())

Submission status: Accepted

Solution code:
import itertools
N,M,Q=map(int,input().split())
a_b_c_d=[list(map(int,input().split())) for _ in range(Q)]
nums=[i for i in range(1,M+1)]
A_s=itertools.combinations_with_replacement(nums,N)
ans=0
for A in A_s:
    tmp=0
    for i in range(Q):
        if A[a_b_c_d[i][1]-1]-A[a_b_c_d[i][0]-1]==a_b_c_d[i][2]:
            tmp+=a_b_c_d[i][3]
    if tmp>ans:
        ans=tmp
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())

ans = 0
for A in itertools.combinations_with_replacement(range(1, m+1), n):
    tmp = 0
    for i in range(q):#i番目の得点を計算
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            tmp += d[i]
    ans = max(ans, tmp)#最大化
    
print(ans)

Submission status: Accepted

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

suretu = list(itertools.combinations_with_replacement(list(range(1,M+1)),N))
arr = [list(map(int, input().split())) for _ in range(Q)]

max_point = 0
for item in suretu:
    point =0
    for jtem in arr:
        if item[jtem[1]-1] - item[jtem[0]-1] == jtem[2]:
            point += jtem[3]

    if point > max_point:
        max_point = point

print(max_point)

Submission status: Accepted

Solution code:
N ,M ,Q = map(int,input().split())
l = [list(map(int,input().split())) for i in range(Q)]
ans=[]
score = 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]
                                        for a, b, c, d in l:
                                            if A[b-1] - A[a-1] == c:
                                                score += d
                                            else:
                                                pass
                                        ans.append(score)
                                        score = 0
print(max(ans))

Submission status: Accepted

Solution code:
import itertools
n,m,q=map(int,input().split())
X=[]
B=[]
for i in range(q):
    X.append(list(map(int,input().split())))
for A in itertools.combinations_with_replacement(range(1,m+1),n):
    ans=0
    for x in X:
        if A[x[1]-1]-A[x[0]-1]==x[2]:
            ans+=x[3]
    B.append(ans)
print(max(B))

Submission status: Accepted

Solution code:
import itertools
n, m, q = map(int, input().split())
abcd = [tuple(map(int, input().split())) for _ in range(q)]
ans = 0
for com in itertools.combinations_with_replacement(range(1, m + 1), n):
    score = sum([d for a, b, c, d in abcd if com[b - 1] - com[a - 1] == c])
    ans = max(ans, score)
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools

def main():
    N, M, Q = map(int, input().split())
    ABCD = [[int(_) for _ in input().split()] for i in range(Q)]
    value_range = list(range(1, M+1))
    seq_list = list(itertools.combinations_with_replacement(value_range, N))

    max_score = 0
    for i_seq in seq_list:
        score = 0
        for a, b, c, d in ABCD:
            if (i_seq[b-1] - i_seq[a-1]) == c:
                score += d

        max_score = max(max_score, score)

    print(max_score)
    return

if __name__ == '__main__':
    main()
    sys.exit(0)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement


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

max_total = 0

A_ls = list(combinations_with_replacement(range(1, M+1), N))

for A in A_ls:
    total = 0
    for i in range(Q):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            total += d[i]
    max_total = max(max_total, total)

print(max_total)

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

nums=[[0,0,0,0]for i in range(Q)]
ans =[]
for i in range(Q):
    nums[i] = list(map(int, input().split()))

for A in As:
    t=0
    for i in range(Q):
        if A[nums[i][1]-1]-A[nums[i][0]-1] == nums[i][2]:
            t += nums[i][3]  

    ans.append(t)

print(max(ans))

Submission status: Accepted

Solution code:
def setse(s, m, i):
    if i < 0:
        return
    s[i] += 1
    if s[i] > m:
        setse(s, m, i - 1)
        if i > 0:
            s[i] = s[i - 1]

n, m, q = map(int, input().split(' '))
a = []
j = [1] * n
sc, scm = 0, 0
for i in range(q):
    al = list(map(int, input().split(' ')))
    a.append(al)
while(j[0] <= m):
    for i in a:
        sc += i[3] if j[i[1] - 1] - j[i[0] - 1] == i[2] else 0
    setse(j, m, n - 1)
    scm = sc if scm < sc else scm
    sc = 0
print(scm)

Submission status: Accepted

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

A = [0] * N
A[0] = 1
result = []


def dfs(d, n, A):
    # 深さがNを超えるか、数字がMを超えたらreturn
    if d > N or n > M:
        return
    # 深さdの数字にnを入力
    A[d - 1] = n

    # 最深まで値が入ったら総和を計算
    if d == N:
        total = 0
        for i in range(Q):
            ai = abcd[i][0]
            bi = abcd[i][1]
            ci = abcd[i][2]
            di = abcd[i][3]
            if A[bi - 1] - A[ai - 1] == ci:
                total += di
        result.append(total)

    dfs(d + 1, n, A)
    dfs(d, n + 1, A)


dfs(2, 1, A)

print(max(result))

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

ans = 0
_N = N
if N < M:
    _N = M

for A in combinations_with_replacement(range(1, M + 1), _N):
    tmp = 0
    for a, b, c, d in L:
        if a <= _N and b <= _N and A[b - 1] - A[a - 1] == c:
            tmp += d

    if tmp > ans:
        ans = tmp

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.buffer.readline
n,m,q=map(int,input().split())
Q=[list(map(int,input().split())) for _ in range(q)]
ans=0
def dfs(i,tab,ma):
	global ans
	if i==n:
		t=0
		for a,b,c,d in Q:
			if tab[b-1]-tab[a-1]==c:
				t+=d
		if t>ans:
			ans=t
		return
	for j in range(ma,m+1):
		dfs(i+1,tab+[j],j)
dfs(0,[],1)
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

print(ans)

Submission status: Accepted

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

def score(A):
    ans = 0
    for i in abcd:
        if A[i[1] -1] - A[i[0] -1] == i[2]:
            ans += i[3]
    return ans

def dfs(A, i):# 数列Aのi番目まで決まってる
    ans = 0
    if i == N:
        return score(A)
    
    lower = 1
    if i != 0:
        lower = A[i-1]
    for x in range(lower, M+1):
        A[i] = x
        ans = max(ans, dfs(A, i+1))
    
    return ans

print(dfs([None]*N, 0))