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:
def main():
    n, m, q = map(int, input().split())
    abcd = [list(map(int, input().split())) for _ in [0]*q]

    que = [[1]]
    for _ in range(n):
        que2 = []
        for qq in que:
            i = qq[-1]
            for j in range(i, m+1):
                que2.append(qq+[j])
        que = que2

    ans = 0
    for q in que:
        temp = 0
        for a, b, c, d in abcd:
            if q[b]-q[a] == c:
                temp += d
        ans = max(ans, temp)
    print(ans)


main()

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

N, M, Q = LI()
ABCD = LRI(Q)

def calc(A):
    ret = 0

    for a, b, c, d in ABCD:
        if A[b] - A[a] == c:
            ret += d
    
    return ret


def bfs(A):
    ans = 0
    stack = collections.deque(A)

    while stack:
        s = stack.popleft()
        
        if len(s) < N+1:
            back = s[-1]
            while back <= M:
                stack.append(s + [back])
                back += 1
        else:
            ans = max(ans, calc(s))

    return ans

print(bfs([[1]]))

Submission status: Accepted

Solution code:
import itertools

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

#print(numbers)


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

ans = 0
for suuretu in suuretus:
    tmp = 0

    if len(suuretu) == N:
#        print(suuretu)
        for number in numbers:
            if suuretu[number[1]-1] - suuretu[number[0]-1] == number[2]:
                tmp += number[3]
        
    ans = max(ans, tmp)
#    print(ans)

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

N, M, Q = LI()
ABCD = LRI(Q)

def calc(A):
    ret = 0

    for a, b, c, d in ABCD:
        if A[b] - A[a] == c:
            ret += d
    
    return ret


def dfs(A):
    ans = 0
    stack = A

    while stack:
        s = stack.pop()
            
        if len(s) < N+1:
            back = s[-1]
            while back <= M:
                stack.append(s + [back])
                back += 1
        else:
            ans = max(ans, calc(s))

    return ans

print(dfs([[1]]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
import itertools

n, m, q = list(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] = list(map(int, input().split()))
    a[i] -= 1
    b[i] -= 1
# Aは単調増加数列でNこの要素を持って最大でもMまで
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:
n,m,q=map(int,input().split())
l=[]
for i in range(q):
    l.append([int(x) for x in input().split()])
for i in range(q):
    l[i][0]-=1
    l[i][1]-=1
result=0
for i0 in range(1,m+1):
    for i1 in range(i0,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):
                                        a=[i0,i1,i2,i3,i4,i5,i6,i7,i8,i9]
                                        score=0
                                        for i in l:
                                            if a[i[1]]-a[i[0]]==i[2]:
                                                score+=i[3]
                                        result=max(score,result)
print(result)

Submission status: Accepted

Solution code:
import itertools
N, M, Q = map(int, input().split())
abcd = list()
for i in range(Q):
    a,b,c,d = map(int, input().split())
    abcd.append((a,b,c,d))
iters = itertools.combinations_with_replacement(range(1, M+1), N)
ans = 0
for com in iters:
    sum = 0
    for a,b,c,d in abcd:
        if(com[b-1]-com[a-1] == c):
            sum += d
    if(sum > ans):
        ans = sum
print(ans)

Submission status: Accepted

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

from itertools import combinations_with_replacement

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

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

ans = 0
for l in lst:
    tmp = 0
    for a, b, c, d in ABCD:
        if l[b - 1] - l[a - 1] == c:
            tmp += d
    ans = max(tmp, ans)
    
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc165/submissions/12600948
# 写経

def main():
    from collections import deque
    import sys
    sys.setrecursionlimit(10 ** 7)

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

    abcd = []
    for _ in range(Q):
        a, b, c, d = map(int, input().split())
        abcd.append((a - 1, b - 1, c, d))

    A = deque([1])

    def rec():
        if len(A) == N:
            return sum(d for a, b, c, d in abcd if A[b] == A[a] + c)

        ret = 0
        for x in range(A[-1], M + 1):
            A.append(x)
            ret = max(ret, rec())
            A.pop()
        return ret

    print(rec())


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

ans = 0
def dfs(now,last,use):
    #print(now,last,use)
    if now == n:
        res = 0
        for a,b,c,d in abcd:
            if use[b-1] - use[a-1] == c:
                res += d
        return res
    res = 0
    for to in range(last,m+1):
        res = max(res, dfs(now+1, to, use + [to]))
    return res

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

Submission status: Accepted

Solution code:
N,M,Q=map(int,input().split())
a=[]
b=[]
c=[]
d=[]
for i in range(Q):
  ta,tb,tc,td=map(int,input().split())
  a+=[ta]
  b+=[tb]
  c+=[tc]
  d+=[td]
maxs=0
A=[0 for i in range(10)]
for i in range(M):
  for j in range(i,M):
    for k in range(j,M):
      for l in range(k,M):
        for m in range(l,M):
          for n in range(m,M):
            for o in range(n,M):
              for p in range(o,M):
                for q in range(p,M):
                  for r in range(q,M):
                    A[0]=i
                    A[1]=j
                    A[2]=k
                    A[3]=l
                    A[4]=m
                    A[5]=n
                    A[6]=o
                    A[7]=p
                    A[8]=q
                    A[9]=r
                    su=0
                    for z in range(Q):
                      if A[b[z]-1]-A[a[z]-1]==c[z]:
                        su+=d[z]
                    if su>maxs:
                      maxs=su
print(maxs)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def combinationWithRepetitionListRecursive(data, r):
  if r <= 0:
    return []

  result = []
  _combinationWithRepetitionListRecursive(data, r, 0, [], result)
  return result

def _combinationWithRepetitionListRecursive(data, r, start, progress, result):
  if r == 0:
    result.append(progress)
    return

  for i in range(start, len(data)):
    _combinationWithRepetitionListRecursive(data, r - 1, i, progress + [data[i]], result)


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

L = [[0] * 4 for _ in range(Q)]

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

#print(L)

allnum = []

for i in range(1, M+1):
    allnum.append(i)

allseq = combinationWithRepetitionListRecursive(allnum, N)
#print(allseq)

MAX = 0

for j in range(len(allseq)):
    point = 0
    for k in range(Q):
        if allseq[j][L[k][1]-1] - allseq[j][L[k][0]-1] == L[k][2]:
            point += L[k][3]
    MAX = max(MAX, point)

print(MAX)

Submission status: Accepted

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

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

ans = 0

import itertools
for seq in itertools.combinations_with_replacement(range(1,m+1),n):
    tmp = 0
    for a,b,c,d in abcd:
        if seq[b-1] - seq[a-1] == c:
            tmp += d

    ans = max(tmp,ans)

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
def main():
    #入力
    readline=stdin.readline
    N,M,Q=map(int,readline().split())
    a=[]
    b=[]
    c=[]
    d=[]
    for i in range(Q):
        li=list(map(int,readline().split()))
        a.append(li[0])
        b.append(li[1])
        c.append(li[2])
        d.append(li[3])

    As=[]
    de=[]
    for i in range(1,M+1):
        de.append([i])
    de=deque(de)
    while len(de)>=1:
        x=de.popleft()
        if len(x)==N:
            As.append(x)
        else:
            n=x[-1]
            for i in range(n,M+1):
                y=x[:]
                y.append(i)
                de.append(y)

    max_res=0
    for i in range(len(As)):
        A=As[i]
        res=0
        for j in range(Q):
            if A[b[j]-1]-A[a[j]-1]==c[j]:
                res+=d[j]
        max_res=max(max_res,res)
    print(max_res)
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

def check(l,c):
    if l[c[1]-1] - l[c[0]-1] == c[2]:
        return True
    else:
        return False

n,m,q = LI()
li = LLI(q)
num = [i for i in range(1,m+1)]
a =  list(itertools.combinations_with_replacement(num, n))
ans = 0
ans_li = []
for suuretsu in a:
    ans = 0 #数列を1つ決める
    for ch in li: #チェックしたいやつを決める
        if check(suuretsu,ch):
            ans += ch[3]
    ans_li.append(ans)
print(max(ans_li))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**6)

n,m,q = map(int,input().split())
E = [list(map(int,input().split())) for i in range(q)]
def dfs(l,string):
  if l == n:
    global ans
    ans = max(ans,check(string));return
  for i in range(int(string[-1]),m+1):
    dfs(l+1,(string+[str(i)]).copy())

def check(string):
  global count
  count += 1
  re = 0
  for a,b,c,d in E:
    if int(string[b])-int(string[a]) == c:
      re += d
  # print(string,re)
  return re
dfs(0,[1])
print(ans)
# print(count)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc165/submissions/12605117
# 写経

def main():
    from itertools import combinations_with_replacement
    import numpy as np

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

    abcd = []
    for _ in range(Q):
        a, b, c, d = map(int, input().split())
        abcd.append((a - 1, b - 1, c, d))

    temp_As = np.array(
        tuple(combinations_with_replacement(
            iterable=range(1, M + 1),
            r=N
        )), dtype=np.int32
    )

    scores = np.zeros(len(temp_As), dtype=np.int32)
    for a, b, c, d in abcd:
        cond = temp_As[:, b] - temp_As[:, a] == c
        scores += d * cond

    print(scores.max())


if __name__ == '__main__':
    main()

# a = np.array([0] * 4)
# a += range(4)
# # array([0, 1, 2, 3])

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

L = [i for i in range(1, M+1)]

iterations = combinations_with_replacement(L, N)

max_score = 0
for v in iterations:
    score = 0
    for i in range(Q):
        if v[b[i]-1] -  v[a[i]-1] == c[i]:
            score += d[i]
    if score > max_score:
        max_score = score

print(max_score)

Submission status: Accepted

Solution code:
def dfs(A):
    global ans
    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


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:
from itertools import combinations_with_replacement
def solve():
    n, m, q = map(int, input().split())
    l = [list(map(int, input().split())) for _ in range(q)]

    com = [int(x) for x in range(1, m+1)]
    ans = 0
    for i in combinations_with_replacement(com, n-1):
        cur = list(i)
        A = [1] + cur
        tot = 0
        for k in range(q):
            a, b, c, d = l[k]
            if A[b-1] - A[a-1] == c:
                tot += d
        ans = max(ans, tot)
    
    return ans


print(solve())

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import defaultdict
    sys.setrecursionlimit(10 ** 6)
    input = sys.stdin.readline
    N, M, Q = [int(x) for x in input().strip().split()]
    abcd = [0] * Q
    for q in range(Q):
        abcd[q] = [int(x) for x in input().strip().split()]

    abcd.sort(key=lambda x:(x[0],x[1]))
    vecs = []

    def makevecs(n, vecs, A):
        if n == N:
            vecs.append(A)
            return None
        for b in range(A[-1], M+1):
            makevecs(n+1, vecs, A+[b])
        return None
        
    makevecs(1, vecs, [1])
    ans = 0
    for vec in vecs:
        ans_ = 0
        for q in range(Q):
            a, b, c, d = abcd[q]
            if vec[b-1] - vec[a-1] == c:
                ans_ += d
        
        ans = max(ans, ans_)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m,q = map(int,input().split())
abcd = [list(map(int,input().split())) for i in range(q)]
ls = [1]
ans=0
def dfs(n,m,i,ls,abcd):
    global ans
    temp=0
    if len(ls)==n:
        for j in abcd:
            if ls[j[1]-1] - ls[j[0]-1] == j[2]:
                temp+=j[3]
        ans=max(ans,temp)
    else:
        for j in range(i,m+1):
            dfs(n,m,j,ls+[j],abcd)
dfs(n,m,1,ls,abcd)
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)]
tl=itertools.combinations_with_replacement(range(1,M+1),N)
ans=0
for l in tl:
    t=0
    for a,b,c,d in ABCD:
        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())
X = [list(map(int, input().split())) for _ in range(Q)]

lst = [list() for _ in range(N + 1)]

for a, b, c, d in X:
    lst[b].append((a, c, d))


class Test:
    def __init__(self):
        self.max_ = 0

    def helper(self, idx, cnt, stack, tmp):
        if cnt == N + 1:
            self.max_ = max(self.max_, tmp)
            return

        for s, t, u in lst[cnt]:
            if stack[cnt - 1] - stack[s - 1] == t:
                tmp += u

        for i in range(idx, M + 1):
            stack.append(i)
            self.helper(i, cnt + 1, stack, tmp)
            stack.pop()


t = Test()
t.helper(1, 0, [], 0)

print(t.max_)

Submission status: Accepted

Solution code:
import itertools

n, m, q = map(int, input().split())
con = list()
ans = 0

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

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

for A in A_li:
    now_score = 0
    for a,b,c,d in con:
        a-=1
        b-=1
        if A[b]-A[a] == c:
            now_score += d
    ans = max(ans, now_score)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools
n,m,q = map(int,input().split())
target = [list(map(int,input().split())) for _ in range(q)]
ans = 0
for A in itertools.combinations_with_replacement(range(1,m+1),n):
  count = sum([abcd[3] for abcd in target if A[abcd[1]-1] - A[abcd[0]-1] == abcd[2]])
  ans = max(ans,count)
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(m), n):
  tmp = 0
  for i in range(q):
    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:
# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

N, M, Q = LI()
ABCD = LRI(Q)

def calc(A):
    ret = 0

    for a, b, c, d in ABCD:
        if A[b] - A[a] == c:
            ret += d
    
    return ret

ans = 0
def dfs(A):
    global ans
    
    if len(A) == N+1:
        ans = max(ans, calc(A))
        return
    
    back = A[-1]
    while back <= M:
        dfs(A + [back])
        back += 1

dfs([1])

print(ans)

Submission status: Accepted

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

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

ans = 0
for a1 in range(1, 11):
    for a2 in range(a1, 11):
        for a3 in range(a2, 11):
            for a4 in range(a3, 11):
                for a5 in range(a4, 11):
                    for a6 in range(a5, 11):
                        for a7 in range(a6, 11):
                            for a8 in range(a7, 11):
                                for a9 in range(a8, 11):
                                    for a10 in range(a9, 11):
                                        # print(a1, a2, a3, a4, a5, a6, a7, a8, a9, a10)
                                        A = [0, a1, a2, a3, a4, a5, a6, a7, a8, a9, a10]
                                        ans_ = 0
                                        if max(A) <= m:
                                            for i in range(q):
                                                if A[abcd[i][1]] - A[abcd[i][0]] == abcd[i][2]:
                                                    ans_ += abcd[i][3]
                                        ans = max(ans_, ans)

print(ans)

Submission status: Accepted

Solution code:
import itertools

n, m, q = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(q)]
mx=0
l=itertools.combinations_with_replacement(range(1,m+1),n)
for y in l:
    temp=0
    for a, b, c, d in x:
        if y[b-1] - y[a-1] == c:
            temp += d
    mx=max(mx,temp)
print(mx)

Submission status: Accepted

Solution code:
import copy


def dfs(A):
    global ans
    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(copy.copy(A))
        A[-1] += 1


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:
from sys import stdin
import itertools
N,M,Q = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for i in range(Q):
    a,b,c,d = [int(x) for x in stdin.readline().rstrip().split()]
    data.append((a,b,c,d))
    
ite = []
def f(n,cnt):
    if cnt == N:
        ite.append(n)
        return
    for i in range(1,M+1):
        if n[-1] <= i:
            f(n+[i],cnt+1)
f([1],0)
ans = 0
for i in ite:
    tmp = 0
    for a,b,c,d in data:
        if i[b-1] - i[a-1] == c:
            tmp += d
    ans = max(ans,tmp)
    
print(ans)

Submission status: Accepted

Solution code:
import itertools

def c165(n, m, q, adli):

    ans = 0
    li = list(itertools.combinations_with_replacement(range(1,m+1), n))
    for i in li:
        count = 0
        for a, b, c, d in adli:
            if i[b-1] - i[a-1] == c:
                count += d
        ans = max(ans, count)

    return ans

def main():
    n, m, q = map(int, input().split())
    adli = [list(map(int, input().split()))for i in range(q)]
    print(c165(n, m, q, adli))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0

for A in itertools.combinations_with_replacement(range(1,M + 1),N):
  temp = 0
  for p in pair:
    if A[p[1]-1] - A[p[0]-1] == p[2]:
      temp += p[3]
      ans = max(ans,temp)
    
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as cwd

N, M, Q = map(int, input().split())
A = list(cwd(range(1, M + 1), N))
ABCD = []

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

res = 0
for i in A:
    tmp = 0
    for j in ABCD:
        if i[j[1]] - i[j[0]] == j[2]:
            tmp += j[3]
    res = max(res, tmp)

print(res)

Submission status: Accepted

Solution code:
N, M, Q, *ABCD = map(int, open(0).read().split())

def solve(A):
    if len(A) == N:
        return sum(d for a, b, c, d in zip(*[iter(ABCD)] * 4) if A[b - 1] - A[a - 1] == c)

    return max(solve(A + [i]) for i in range(A[-1], M + 1))

print(solve([1]))

Submission status: Accepted

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

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

def f(index,li):
    if index == n:
        return eva(li)
    else:
        ret = 0
        t = 1
        if index>=1:
            t = li[index-1]
        for i in range (t,m+1):
            li[index]=i
            x = f(index+1,li)
            if ret < x:
                ret = x
        return ret
    
def eva(li):
    tmp = 0
    for k in range(q):
        a = lst[k][0]
        b = lst[k][1]
        c = lst[k][2]
        d = lst[k][3]
        if li[b-1]-li[a-1]==c:
            tmp = tmp + d
    return tmp
    
print(f(0,y))

Submission status: Accepted

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

for A in combinations_with_replacement(range(1, M+1), N):
    point = sum([d for a, b, c, d in Req if A[b-1] - A[a-1] == c])
    ans = max(ans, point)
    
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)]
ls = [1]
ans=0
def dfs(n,m,i,ls):
    global ans
    global abcd
    temp=0
    if len(ls)==n:
        for j in abcd:
            if ls[j[1]-1] - ls[j[0]-1] == j[2]:
                temp+=j[3]
        ans=max(ans,temp)
    else:
        for j in range(i,m+1):
            dfs(n,m,j,ls+[j])
dfs(n,m,1,ls)
print(ans)

Submission status: Accepted

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

temp = [[i] for i in range(M)]
lsts = []
while temp:
    q = temp.pop()
    if len(q) == N:
        lsts.append(q)
        continue
    for i in range(q[-1], M):
        q1 = q[:]
        q1.append(i)
        temp.append(q1)
lsts.sort()  
ans = []
for lst in lsts:
    cnt = 0
    for k in abcd:
        if lst[k[1]-1] - lst[k[0]-1] == k[2]:
            cnt += k[3]
    ans.append(cnt)
print(max(ans))

Submission status: Accepted

Solution code:
import itertools
n,m,q = map(int,input().split())
target = [list(map(int,input().split())) for _ in range(q)]
ans = 0

for A in itertools.combinations_with_replacement(range(1,m+1),n):
  count = 0
  for abcd in target:
    if A[abcd[1]-1] - A[abcd[0]-1] == abcd[2]:
      count += abcd[3]
  
  ans = max(ans,count)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import itertools

N,M,Q=map(int, sys.stdin.readline().split())
X=[ map(int, sys.stdin.readline().split()) for _ in range(Q) ]

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

ans=float("-inf")
for L in LL:
    temp_ans=0
    for a,b,c,d in X:
        if L[b-1]-L[a-1]==c:
            temp_ans+=d
    ans=max(ans,temp_ans)
print ans

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
N, M, Q = map(int, input().split())
a_list = [list(map(int, input().split())) for i in range(Q)]

temp_list = []

max_count = 0


def solve(i, j):
    global max_count
    if i == N:
        temp_count = 0

        for m in a_list:
            if j[m[1] - 1] - j[m[0] - 1] == m[2]:
                temp_count += m[3]
        if max_count < temp_count:
            max_count = temp_count

        return

    a = 0
    if len(j) > 0:
        a = j[-1]
    else:
        a = 1
    for k in range(a, M + 1):
        solve(i + 1, j + [k])


solve(0, [])
print(max_count)

Submission status: Accepted

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

def eval(a):
  score = 0
  for c in constraints:
    if a[c[1] - 1] - a[c[0] - 1] == c[2]:
      score += c[3]
  return score

# a: 長さNの配列, i番目以前の要素は値が決まっていて、それ以降は未定
def dfs(a, i):
  if i == n:
    return eval(a)
  score = 0
  for x in range(a[i - 1] if 0 < i else 1, m + 1):
    a[i] = x
    score = max(score, dfs(a, i + 1))
  return score

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

Submission status: Accepted

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

# いくつか入力
n,m,q = (int(i) for i in input().split())
answer = 0
# n行の複数列ある数値を二次元配列へ。x[q][?]
e = [[int(i) for i in input().split()] for i in range(q)] 
a=[1]*10
for i1 in range(1,m+1):
    a[1] = i1
    for i2 in range(i1,m+1):
        a[2] = i2
        for i3 in range(i2,m+1):
            a[3] = i3
            for i4 in range(i3,m+1):
                a[4] = i4
                for i5 in range(i4,m+1):
                    a[5] = i5
                    for i6 in range(i5,m+1):
                        a[6] = i6
                        for i7 in range(i6,m+1):
                            a[7] = i7
                            for i8 in range(i7,m+1):
                                a[8] = i8
                                for i9 in range(i8,m+1):
                                    a[9] = i9
                                    t=0
                                    for i in range(q):
                                        if a[e[i][1]-1] - a[e[i][0]-1] == e[i][2]:
                                            t += e[i][3]
                                        answer = max(t,answer)

print(answer)