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:
#!/usr/bin/env python3
import sys
import functools
sys.setrecursionlimit(10**8)
INF = float("inf")


def solve(N: int, M: int, Q: int,
          a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):

    # 全列挙行けるかを確認
    @functools.lru_cache(maxsize=None)
    def f(n, m):
        if n == 1:
            return m
        ret = 0
        for i in range(m, 0, -1):
            ret += f(n-1, i)
        return ret
    # print(f(N, M))

    samples = []
    # 全列挙

    def rec(curr, lower, d):
        # d: 今の深さ
        if d < N:
            for i in range(lower, M+1):
                rec(curr+[i], i, d+1)
        else:
            for i in range(lower, M+1):
                samples.append(curr+[i])

    max_tot = -INF
    rec([], 1, 1)

    # print(len(samples))
    for A in samples:  # 10^5程度のループ
        # print(A)
        tot = 0
        for aa, bb, cc, dd in zip(a, b, c, d):
            if A[bb-1] - A[aa-1] == cc:
                tot += dd
        max_tot = max(tot, max_tot)
    print(max_tot)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    a = [int()] * (Q)  # type: "List[int]"
    b = [int()] * (Q)  # type: "List[int]"
    c = [int()] * (Q)  # type: "List[int]"
    d = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
        d[i] = int(next(tokens))
    solve(N, M, Q, a, b, c, d)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,m,q=f()
Q=[list(f())for _ in range(q)]
from itertools import*
print(max(sum(d for a,b,c,d in Q if l[b-1]-l[a-1]==c)for l in combinations_with_replacement(range(m),n)))

Submission status: Accepted

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

ans = 0
def dfs(L):
    global ans
    if len(L) == N+1:
        sumnum = 0
        for i in range(Q):
            if L[b[i]] - L[a[i]]==c[i]:
                sumnum += d[i]
        ans = max(ans, sumnum)
        return 0
    A = L.copy()
    A.append(A[-1])
    while A[-1] <= M:
        dfs(A)
        A[-1]+=1

dfs([1])
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

ans = 0
for a in itertools.combinations_with_replacement(range(1, M+1), N):
    ans = max(ans, score(a, abcd))

print(ans)

Submission status: Accepted

Solution code:
def recursion(n,m,curList,res):
    if len(curList) == n:
        res.append(curList.copy())
        return

    for i in range(1,m+1):
        if len(curList) > 0 and i < curList[-1]:
            continue
        curList.append(i)
        recursion(n,m,curList,res)
        curList.remove(curList[-1])

def makeSequenceList(n,m):
    res = []
    recursion(n,m,[],res)
    return res

n,m,q = map(int,input().split())
quadList = []
for i in range(q):
    quad = [int(ch) for ch in input().split()]
    quadList.append(quad)
seqList = makeSequenceList(n,m)
ans = -1
for seq in seqList:
    sum = 0
    for quad in quadList:
        if seq[quad[1]-1] - seq[quad[0]-1] == quad[2]:
            sum += quad[3]
    ans = max(sum,ans)
print(ans)

Submission status: Accepted

Solution code:
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] = map(int, input().split())

A = [0] * (n+1)
A[0] = 1
ans = 0
def dfs(k):
    global ans
    if k == n+1:
        now = 0
        for i in range(q):
            if A[b[i]] - A[a[i]] == c[i]:
                now += d[i]
        ans = max(ans, now)
    else:
        for i in range(A[k-1], m+1):
            A[k] = i
            dfs(k+1)

dfs(1)
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

for i in range(q):
    A,B,C,D=map(int,input().split())
    a.append(A)
    b.append(B)
    c.append(C)
    d.append(D)

p=list(range(1,m+1))
ans=0
cnt=0

for i in itertools.combinations_with_replacement(p, n):
    ans=max(ans,cnt)
    cnt=0
    for j in range(q):
        if i[b[j]-1] - i[a[j]-1]==c[j]:
            cnt+=d[j]

print(max(cnt,ans))

Submission status: Accepted

Solution code:
def c_many_requirements_dfs():
    import sys
    sys.setrecursionlimit(10**6)
    N, M, Q = [int(i) for i in input().split()]
    Queries = [[int(i) for i in input().split()] for j in range(Q)]

    def calc_score(seq):
        return sum(d for a, b, c, d in Queries if seq[b - 1] - seq[a - 1] == c)

    def dfs(seq):
        if len(seq) == N:
            return calc_score(seq)

        ret = 0
        left = seq[-1] if seq else 1
        for i in range(left, M + 1):
            ret = max(ret, dfs(seq + [i]))
        return ret
    return dfs([])

print(c_many_requirements_dfs())

Submission status: Accepted

Solution code:
def c_many_requirements():
    from itertools import combinations_with_replacement as h
    N, M, Q = [int(i) for i in input().split()]
    Queries = [[int(i) for i in input().split()] for j in range(Q)]

    def calc_score(seq):
        return sum(d for a, b, c, d in Queries if seq[b - 1] - seq[a - 1] == c)
    return max([calc_score(sequence) for sequence in h(range(1, M + 1), N)])

print(c_many_requirements())

Submission status: Accepted

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

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(array):
        res = 0
        for a, b, c, d in query:
            if array[b-1]-array[a-1] == c:
                res += d
        return res

    A = [0]*N

    def dfs(idx):
        global ans
        if idx == N:
            ans = max(getScore(A), ans)
        else:
            if idx == 0:
                k = 1
            else:
                k = A[idx-1]
            for i in range(k, M+1):
                A[idx] = i
                dfs(idx+1)

    dfs(0)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0
def dfs(A):
    #print(A)
    global ans 
    if len(A) == n+1:
        tmp = 0
        for a,b,c,d in li:
            if A[b] - A[a] == c:
                tmp += d
            ans = max(ans,tmp)
        return
    for i in range(A[len(A)-1],m+1):
        dfs(A+[i])
dfs([1])
print(ans)

Submission status: Accepted

Solution code:
import itertools

n, m, q = map(int, input().split())
a = [0 for i in range(q)]
b = [0 for i in range(q)]
c = [0 for i in range(q)]
d = [0 for i in range(q)]

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

score = 0
for SR in itertools.combinations_with_replacement(range(1, m+1), n):
    now = 0
    for i in range(q):
        now += d[i] if SR[b[i]-1] - SR[a[i]-1] == c[i] else 0
    score = max(score, now)

print(score)

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
q_list = list()
for _ in range(Q):
     q_list.append( tuple( map(int, input().split()) ) )

from itertools import combinations_with_replacement
A_conbi = combinations_with_replacement(range(1,M+1), N)

max_v = 0
for A in A_conbi:
    sum_v = 0
    for a,b,c,d in q_list:
        if A[b-1]-A[a-1] == c:
            sum_v = sum_v + d
    max_v = max(max_v, sum_v)

print(max_v)

Submission status: Accepted

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

max_score=0

num=[0]*n
while True:
    score=0
    for lis in abcd:
        if num[lis[1]-1]-num[lis[0]-1]==lis[2]:
            score+=lis[3]
    if score>=max_score:
        max_score=score
    num[-1]+=1
    #繰り上がる場合を考える
    if num[-1]==m:
        check=-1
        for j in range(n-1):
            if num[j]!=m-1:
                check=j
        if check==-1:
            break
        else:
            num[check]+=1
            for k in range(check+1,n):
                num[k]=num[check]
print(max_score)

Submission status: Accepted

Solution code:
import itertools

N, M, Q = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(Q)]
data = list(range(1, M + 1))
L = list(itertools.combinations_with_replacement(data, N))
ans = 0
for l in L:
    tmp = 0
    for a, b, c, d in X:
        if l[b - 1] - l[a - 1] == c:
            tmp += d
    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)]

result = 0
for A in combinations_with_replacement(range(1, M + 1), N):
#1,2,...,Mの数列から重複込みでN文字の文字列を作る
    t = 0
    for a, b, c, d in abcd:
        if A[b - 1] - A[a - 1] == c:
            t += d
    result = max(result, t)
print(result)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, m, q  = map(int, input().split())
abcd  = [tuple(map(int, input().split())) for i in range(q)]

ans = 0

def check(A):
    global ans
    max_ = 0

    # 点数計算
    for (a, b, c, d) in abcd:
        if A[b-1] - A[a-1] == c:
            max_ += d

    # 最大値更新
    ans = max(ans, max_)

def suretu(A=[], st=1):
    # 再帰的に数字を1つずつ足してって数列生成
    for i in range(st, m+1):
        if len(A) == n: # 数列完成
            check(A)
            return
        else:
            suretu(A + [i], i)

    return ans

print(suretu())

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,m,q=f()
lq=[tuple(f()) for _ in range(q)]
ans=0
from itertools import *
for t in combinations_with_replacement(range(m),n):
  s=0
  for a,b,c,d in lq:
    if t[b-1]-t[a-1]==c: s+=d
  ans=max(ans,s)
print(ans)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest

sys.setrecursionlimit(10**5)

def search(seq, min_n, max_n, n, req):
	ans = 0
	if len(seq) == n:
		for a, b, c, d in req:
			if seq[b-1] - seq[a-1] == c:
				ans += d
		return ans
	else:
		for i in range(min_n, max_n+1):
			new_seq = seq + [i]
			ans = max(ans, search(new_seq, i, max_n, n, req))
	return ans

def resolve():
	n, m, q = map(int, input().split())
	req = [list(map(int, input().split())) for _ in range(q)]
	print(search([], 1, m, n, req))
resolve()

Submission status: Accepted

Solution code:
n, m, q = map(int, input().split())
num = [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):
                  L = [1, i1, i2, i3, i4, i5, i6, i7, i8, i9]
                  A = []
                  for i in range(n):
                    A.append(L[i])
                  tmp = 0
                  for i in range(q):
                    a = num[i][0] - 1
                    b = num[i][1] - 1
                    c = num[i][2]
                    d = num[i][3]
                    if A[b] - A[a] == c:
                      tmp += d
                  ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from itertools import permutations, accumulate
from math import sqrt
from bisect import bisect_left, bisect_right
from copy import deepcopy
import sys
def I(): return int(input())  # '123' -> 123
def Is(): return map(int, input().split())  # '123 456' -> 123, 456
def LI(): return list(map(int, input().split()))  # '123 456' -> [123, 456]
def TI(): return tuple(map(int, input().split()))  # '123 456' -> (123, 456)
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()  # 'aa bb' -> 'aa','bb' or ['aa','bb']
def LS(): return list(input())  # 'abc123' -> ['a','b','c','1','2','3']
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(1000000)
MOD = 1000000007
INF = float('inf')



N, M, Q = Is()
ABCD = TIR(Q)
ans = -INF

def dfs(A):
    global ans
    if len(A) == N:
        score = 0
        for a, b, c, d in ABCD:
            if A[b - 1] - A[a - 1] == c:
                score += d
        ans = max(ans, score)
    else:
        ret = 0
        amax = max(A) if len(A) != 0 else 1
        for i in range(amax, M+1):
            dfs(A + [i])

dfs([])
print(ans)

Submission status: Accepted

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


a=[]
b=[]
c=[]
d=[]
for i in range(0,q):
    ay,by1,cy,dy=map(int,input().split())
    a.append(ay)
    b.append(by1)
    c.append(cy)
    d.append(dy)
s=0
smax=-100

sys.setrecursionlimit(3000)



def dfs(h):
    global smax
    if len(h)==n+1:
        s=0
        for j in range(0,q):
            if h[b[j]]-h[a[j]]==c[j]:
                s+=d[j]
        if s>smax:
            smax=s

        return
    
    for i in range(0,m+1-h[len(h)-1]):
        
        h2=h[:]
        h2.append(h[len(h)-1]+i)
        dfs(h2)

sta=[1]
dfs(sta)
print(smax)

Submission status: Accepted

Solution code:
#dfs試す
n,m,q=map(int, input().split( ))
qs=tuple(tuple(map(int, input().split( ))) for _ in range(q))
ans=0
def dfs(ll):
    global ans
    if len(ll)==n+1:
        sm=0
        for ai,bi,ci,di in qs:
            if ll[bi]-ll[ai]==ci:
                sm+=di 
        ans=max(ans,sm)
    else:
        for i in range(ll[-1],m):#+1
            ll2=ll+[i]
            dfs(ll2)
l=[0]
dfs(l)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)

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

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



def dp(k, key, a):
  if k == 0:
    sub = 0
    for i in range(q):
      if key[abcd[i][1]-1] - key[abcd[i][0]-1] == abcd[i][2]:
        sub += abcd[i][3]
    return max([a, sub])
  elif k == n:
    sub = a
    for i in range(1, m+1):
      sub = max([dp(k-1, key+[i], sub), sub])
    return sub
  else:
    sub = a
    for i in range(key[-1], m+1):
      sub = max([dp(k-1, key+[i], sub), sub])
    return sub

ans = dp(n, [], 0)
print(ans)

Submission status: Accepted

Solution code:
n,m,q = list(map(int,input().split()))
abcd =  [list(map(int,input().split())) for i in range(q)]
 
 
def dfs(x,y,z,que):
    ret = 0
    if x == 0:
        for a,b,c,d in abcd:
            if que[b-1] - que[a-1]==c:
                ret+=d
        return ret
    for i in range(y,z+1):
        ret = max(ret,dfs(x-1,i,z,que + [i]))
    return ret
 
print(dfs(n,1,m,[]))

Submission status: Accepted

Solution code:
from collections import deque

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

S=[]
for i in range(Q):
    S.append(list(map(int,input().split())))
sorted(S, key=lambda x: x[-1])

S0=sorted(S, key=lambda x: x[0],reverse=False)

tmp=deque([str(0)])
out=0
while tmp:
    T=tmp.pop()
    Ans=0
    if len(T)<N:
        for i in range(int(T[-1]),M):
            tmp.append(T+str(i))
    else:
        for i in range(Q):
            S0=S[i]
            if int(T[S0[1]-1])-int(T[S0[0]-1])==S0[2]:
                Ans+=S0[3]
        out=max(out,Ans)
print(out)

Submission status: Accepted

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

def calc_score():
    res = 0
    for i,j,c,d in qd:
        if a[j-1]-a[i-1] == c:
            res += d
    return res

a = []
score = [-1<<31]

def dfs(i,l,depth):  # i location filling # l largest
    if i == n:
        score[0] = max(score[0],calc_score())
        return
    for j in range(l, m+1):
        a.append(j)
        dfs(i+1,j,depth+1)
        a.pop()

dfs(0,1,0)

print(score[0])

Submission status: Accepted

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


A_list = list(itertools.combinations_with_replacement(range(1, M+1), N))
ans = 0
for A in A_list:
    # print(A[0])
    sum = 0
    for a, b, c, d in q_list:
        if A[b-1] - A[a-1] == c:
            sum += d
    ans = max(ans, sum)

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
from pprint import pprint
import itertools

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

ans = 0
for comb in itertools.combinations_with_replacement(list(range(1, m + 1)), n):
    l = list(comb)
    l.sort()
    tmp = 0

    for a, b, c, d in abcd:
        a -= 1
        b -= 1

        if l[b] - l[a] == c:
            tmp += d

    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
import itertools

#19 choose 9
#92378

def main():
    N, M, Q = map(int, input().split())
    Q_l = []
    final_score = 0
    for i in range(Q):
        Q_l.append(list(map(int, input().split())))
    for A in itertools.combinations_with_replacement(range(1, M+1), N):
        score = 0
        for q in Q_l:
            if A[q[1]-1] - A[q[0]-1] == q[2]:
                score += q[3]
            final_score = max([final_score, score])
    print(final_score)
main()

Submission status: Accepted

Solution code:
def digitSum(n):
    # 数値を文字列に変換
    s = str(n)
    # １文字ずつ数値化し配列にする。
    array = list(map(int, s))
    # 合計値を返す
    return sum(array)

def main():
    n,m,q=map(int,input().split())
    data=[]
    ans=0
    for i in range(q):
        a,b,c,d=map(int,input().split())
        data.append([a,b,c,d])
    num=0
    diff=[0]*(n-1)
    res=0
    while num<10**(n-1):
        res=0
        for i in range(q):
            if data[i][2]==sum(diff[data[i][0]-1:data[i][1]-1]):
                res+=data[i][3]
        ans=max(ans,res)
        num+=1
        i=1
        while num<10**n and digitSum(num)>m-1:
            num=(num//10**i)*10**i+10**i
            i+=1
        strDiff=list(str(num).zfill(n-1))
        diff=[int(s) for s in strDiff]
    print(ans)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
# A, B = list(map(int, input().split()))
# S = list(map(input().split())

"""
import itertools
s = []
for i in range(N):
    s.append(int(input()))


for i in range(n):
    x,y = [int(j) for j in input().split()]
    dataX.append(x)
    dataY.append(y)

二次元配列
for i in range(n):
    d.append([int(j) for j in input().split()])

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


c = [[j for j in input()] for i in range(h)]

sp.sort(key=lambda x:(x[1], -x[2]))

コレクションのvalue値を取る時
for v in a.values():
        if v%2!=0:
            even = False

二次元配列
road = [[0]*n]*n　こうやって書くと全部更新されるから
road = [[0]*n for i in range(n)]って書くといい

一番回数の多いもの取得
l = collections.Counter(s)
a = l.most_common()[0][0]

forの逆
for i in reversed(range(0, n)):

順列重複あり
ans = list(itertools.product(l, repeat=n))

l_sorted = sorted(l, key=lambda x: x[1], reverse=True)

a_count = collections.Counter(a)
a_list = list(a_count.items())

"""
from fractions import gcd
from functools import reduce
# from collections import deque
# from math import factorial
# import collections
import math
import sys
sys.setrecursionlimit(2000000)
# import itertools
# import statistics
# import numpy as np
# x = int(input())
n, m, q = list(map(int, input().split()))
# a, b = list(map(int, input().split()))

a = []
b = []
c = []
d = []
abcd = []
for i in range(q):
    x, y, z, k = [int(j) for j in input().split()]
    abcd.append([x, y, z, k])

s = [0]*n
ans = 0


def dfs(s, num, i):
    if i == n:
        global ans
        total = 0
        for j in range(q):
            if s[abcd[j][1]-1]-s[abcd[j][0]-1] == abcd[j][2]:
                total += abcd[j][3]
        ans = max(ans, total)
        return
    else:
        for j in range(num, m+1):
            s[i] = j
            dfs(s, j, i+1)


dfs(s, 1, 0)
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations_with_replacement

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


def main():
    N, M, Q = map(int, input().split())
    abcd = [None] * Q
    for i in range(Q):
        abcd[i] = tuple(map(int, input().split()))

    ans = 0
    for A in combinations_with_replacement(range(1, M+1), N):
        score = 0
        for q in abcd:
            a, b, c, d = q
            if A[b-1] - A[a-1] == c:
                score += d
        if score > ans:
            ans = score

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def maxim(S,N,M,A,j,ans):
    way=0
    for i in range(j,M+1):
        A.append(i)
        #print(A)
        if(len(A)==N):
            #print(A)
            for k in S:
                #print(k)
                if(A[k[1]-1]-A[k[0]-1]==k[2]):
                    way+=k[3]
                else:
                    pass
                #print(way)
            if(way>ans):
                ans=way
            else:
                pass
            way=0
            #print(ans)
        else:
            way=maxim(S,N,M,A,i,ans)
            #print(way)
            #print(A)
            if(way>ans):
                ans=way
            else:
                pass
            way=0
        A.pop(len(A)-1)
        #print(A)
    return ans

N,M,Q=map(int,input().split())
S=[]
A=[]
for i in range(Q):
    S.append(list(map(int,input().split())))
ans=0
ans=maxim(S,N,M,A,1,ans)
print(ans)

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):
    x,y,z,w=map(int,input().split())
    x-=1
    y-=1
    a[i],b[i],c[i],d[i]=x,y,z,w
ans=0
for v in combinations_with_replacement(range(1,m+1),n):
    res=0
    for i in range(q):
        if v[b[i]]-v[a[i]]==c[i]:
            res+=d[i]
    ans=max(ans,res)
print(ans)

Submission status: Accepted

Solution code:
import itertools
 
def check(lis, a):
    return sum((i[3] for i in a if lis[i[1]-1]-lis[i[0]-1]==i[2]))
   
n, m, q = map(int, input().split())
a = [[int(i) for i in input().split(" ")] for j in range(q)]
ans = 0
for i in itertools.combinations_with_replacement(range(m), n):
    ans = max(ans, check(i, a))
print(ans)

Submission status: Accepted

Solution code:
def main():
  import itertools
  n,m,q=map(int,input().split())
  l=[tuple(map(int,input().split())) for _ in range(q)]
  a=[i+1 for i in range(m)]
  ans=0
  for i in itertools.combinations_with_replacement(a,n):
    cnt=0
    for j in range(q):
      ll=l[j]
      if i[ll[1]-1]-i[ll[0]-1]==ll[2]:
        cnt+=ll[3]
    ans=ans if ans>=cnt else cnt
    cnt=0
  print(ans)   
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import itertools

def check(lis, a):
    return sum((i[3] for i in a if lis[i[1]-1]-lis[i[0]-1]==i[2]))
   
n, m, q = map(int, input().split())
a = tuple(tuple(int(i) for i in input().split(" ")) for j in range(q))
ans = 0
for i in itertools.combinations_with_replacement(range(m), n):
    ans = max(ans, check(i, a))
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections

n,m,q = map(int,input().split())
item = []
for i in range(q):
    a,b,c,d = map(int,input().split())
    item.append([a,b,c,d])
a = [0 for i in range(11)]
ans = 0
for i1 in range(1,11):
    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
                                    for i10 in range(i9,m+1):
                                        a[10] = i10
                                        s = 0
                                        for e,f,g,h in item:
                                            if a[f] - a[e] == g:
                                                s+=h
                                        ans = max(ans,s)
print(ans)

Submission status: Accepted

Solution code:
import itertools;n,m,q,*l=map(int,open(0).read().split());print(max(sum(d for a,b,c,d in[l[j*4:j*4+4]for j in range(q)]if i[b-1]-i[a-1]==c)for i in itertools.combinations_with_replacement(range(m),n)))

Submission status: Accepted

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

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

def dfs(k, x):
    global mx
    if k == n:
        v = 0
        for line in query:
            a, b, c, d = line
            if x[b] - x[a] == c: v += d
        if mx < v: mx = v
    else:
        for i in range(x[-1], m + 1):
            dfs(k + 1, x + [i])
    
mx = 0
dfs(0, [1])

print(mx)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from itertools import combinations_with_replacement


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

    result = 0

    for C in combinations_with_replacement(range(1, M + 1), N):
        tmp = sum([d for a, b, c, d in ABCD if C[b - 1] - C[a - 1] == c])
        result = max(result, tmp)
    print(result)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
"""
https://atcoder.jp/contests/abc165/tasks/abc165_c

C - Many Requirements /

制約
2 <= N <= 10
1 <= N <= 10
1 <= Q <= 50
"""
from collections import deque

deq = deque()
al = []

def solve(n,m,q,x):

    max = 0

    for a_list in al:
        cnt = 0
        for a in x:
            if a_list[ a[1]-1 ] - a_list[ a[0]-1 ] == a[2]:
                cnt += a[3]
        if max < cnt:
            max = cnt

    return max

if __name__ == '__main__':
    n, m, q = map(int, input().split())
    x = [list(map(int, input().split())) for i in range(q)]

    #初期値を設定
    deq.append([1])

    #解になる可能性のある数列を生成
    while(deq):
        item = deq.popleft()
        if len(item) != n:
            for i in range(item[-1],m+1):
                deq.append(item + [i])
        else:
            al.append(item)

    #print(*al, sep='\n')
    ans = solve(n,m,q,x)

    print(ans)

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
con=[list(map(int,input().split())) for i in range(q)]
ans=0
from itertools import combinations_with_replacement
ten=[i for i in range(m)]

x=list(combinations_with_replacement(ten,n))
for i in range(len(x)):
  y=list(x[i])
  nowans=0
  for j in range(q):
    if y[con[j][1]-1]-y[con[j][0]-1]==con[j][2]:
      nowans+=con[j][3]
  ans=max(ans,nowans)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

for x in combinations_with_replacement(l,n):
    ans1=0
    x=sorted(x)
    for Q in query:
        if x[Q[1]-1]-x[Q[0]-1] == Q[2]:
            ans1 += Q[3]
    ans = max(ans,ans1)
        
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

query = []
num_list = list(range(m))

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

max_score = 0

for i in combinations_with_replacement(num_list, n):
    score = 0
    for a,b,c,d in query:
        if i[b-1] - i[a-1] == c:
            score += d
    if max_score < score:
        max_score = score

print(max_score)