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 itertools

n,m,q=map(int,input().split())
l=[i for i in range(1,m+1)]
que=list(itertools.combinations_with_replacement(l, n))
point=[0 for i in range(len(que))]
ans=0

for i in range(q):
  a,b,c,d=list(map(int,input().split()))
  a-=1
  b-=1
  for j in range(len(que)):
    if que[j][b]-que[j][a]==c:
      point[j]+=d
print(max(point))

Submission status: Accepted

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

for q in range(Q):
  a_,b_,c_,d_ =map(int,input().split())
  a.append(a_-1)
  b.append(b_-1)
  c.append(c_)
  d.append(d_)
  
def score(A):
  tmp=0
  for q in range(Q):
    if A[b[q]]-A[a[q]]==c[q]:
      tmp += d[q]
  
  return tmp

def dfs(A):
  if len(A)==N:
    return score(A)
  
  elif len(A)==0:
    Alast=1
  
  else:
    Alast=A[-1]
   
  ans=0
    
  for i in range(Alast,M+1):
    A.append(i)
    ans = max(ans,dfs(A))
    A.pop()
  
  return ans
    
print(dfs([]))

Submission status: Accepted

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

aaa = [[1]]
bbb = []

for i in range(n-1):
  for aa in aaa:
    for j in range(aa[-1], m+1):
      tmp = copy.copy(aa)
      tmp.extend([j])
      bbb.append(tmp)
  aaa = bbb
  if i < n-2:
    bbb = []

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

ans = 0
for bb in bbb:
  score = 0
  for i in range(0, len(qs), 4):
    if bb[qs[i+1]-1] - bb[qs[i+0]-1] == qs[i+2]:
      score += qs[i+3]
  ans = max(ans, score)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

def solve(N: int, M: int, Q: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
    from itertools import combinations_with_replacement
    def f(s):
        ret = 0
        for aa, bb, cc, dd in zip(a, b, c, d):
            if s[bb-1] - s[aa-1] == cc:
                ret += dd
        return ret
    return max(map(f, combinations_with_replacement(range(1, M+1), N)))


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
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))
    print(solve(N, M, Q, a, b, c, d))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

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

def dfs(arr,i = 0):
    if i == N:
        score = 0
        for q in range(Q):
            score += A[q][3] if arr[A[q][1]-1] - arr[A[q][0]-1] == A[q][2] else 0
        return score

    max_score = 0
    for n in range(arr[i-1] if i >= 0 else 1, M+1):
        x = [arr[k] if k != i else n for k in range(N)]
        max_score = max(max_score, dfs(x,i+1))
    
    return max_score
        
print(dfs([1 for _ in range(N)]))

Submission status: Accepted

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

ans = []
import itertools
for A in itertools.combinations_with_replacement(range(1, M+1), N):
    tmp = 0
    for a, b, c, d in abcd:
        if A[b-1] - A[a-1] == c:
            tmp += d
    ans.append(tmp)
print(max(ans))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
#input=sys.stdin.readline
sys.setrecursionlimit(3000000)

x=10
def sol(a):
    if len(a)==10:
        tmp=0
        if max(a)<=f[1]:
            for i in w:
                if a[i[1]-1]-a[i[0]-1]==i[2]:
                    tmp+=i[3]
        ans[0]=max(ans[0],tmp)
        return
    s=a[-1] if len(a) else 1
    for i in range(s,10+1):
        a.append(i)
        sol(a)
        a.pop()

ans=[0]
n,m,q=map(int,input().split())
f=[n,m]
w=[]
for i in range(q):
    a,b,c,d=map(int,input().split())
    w.append((a,b,c,d))
#for i in w:
#    print(i)
sol([])
print(ans[0])

Submission status: Accepted

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10

N, M, Q = [int(x) for x in stdin.readline().rstrip().split()]
abcd = [list(map(int, stdin.readline().rstrip().split())) for _ in range(Q)]

ans = 0

nums = [i for i in range(1, M+1)]
A = list(itertools.combinations_with_replacement(nums, N))

for l in A:
    l = (0,) + l 
    tmp_ans = 0
    for a, b, c, d in abcd:
        if l[b] - l[a] == c:
            tmp_ans += d


    
    ans = max(ans, tmp_ans)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# Atcoder necoak answer
# https://atcoder.jp/contests/abc165/tasks/abc165_c

import numpy as np
from itertools import combinations_with_replacement

# def create_list(tmp_anslist, zan_length, zan_num_list):
#     if zan_length == 0:
#         anslist_candidates.append(tmp_anslist)
#         return
#     
#     for i, num in enumerate(zan_num_list):
#         more_zan_num_list = zan_num_list[i:]
#         create_list(tmp_anslist + [num], zan_length-1, more_zan_num_list)

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

# abcd_array = np.empty((Q, 4), dtype=int)
abcd_array = []
for i in range(Q):
    abcd = map(int, input().split())
    abcd_array.append(list(abcd))
# print(abcd_array)

# anslist_candidates = []
# create_list([], N, [ax for ax in range(1, M+1)])
# print(anslist_candidates)

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


max_anslist_score = 0
for tmp_anslist in anslist_candidates:
    sum_d = 0

    is_valid_anslist = True
    prev_ansitem = tmp_anslist[0]
    for ansitem in tmp_anslist[1:]:
        if prev_ansitem > ansitem:
            is_valid_anslist = False
            break
    if not is_valid_anslist:
        continue

    for ai, bi, ci, di in abcd_array:
        #print('ai:%d, bi:%d, ci:%d, di:%d' % (ai, bi, ci, di))
        #print('tmp_anslist:%s' % (tmp_anslist))
        if ((tmp_anslist[bi-1] - tmp_anslist[ai-1]) == ci):
            sum_d += di
    #print('%s : %d' % (tmp_anslist, sum_d))
    max_anslist_score = max(max_anslist_score, sum_d)

print(max_anslist_score)

Submission status: Accepted

Solution code:
from functools import lru_cache
import sys

#@lru_cache(maxsize=1000)
def dfs(A,B):
    if len(A)==n:
        ans=0
        for i in num_list:
            if A[i[1]-1]-A[i[0]-1]==i[2]:
                ans+=i[3]
        B.append(ans)
        return
    for i in range(max(A),m+1):
        A.append(i)
        dfs(A,B)
        A.pop()
if __name__=="__main__":
    sys.setrecursionlimit(10000)
    n,m,q=map(int,input().split())
    num_list=[]
    ans_lst=[]
    for i in range(q):
        tmp=list(map(int,input().split()))
        num_list.append(tmp)
    a=[]
    for i in range(1,m+1):
        a.append(i)
        dfs(a,ans_lst)
        a.clear()
    print(max(ans_lst))

Submission status: Accepted

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

print(ans)

Submission status: Accepted

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

query = []

for _ in range(Q):
    query.append(tuple(map(int, input().split())))

res = 0


def solve(A):
    global res
    if len(A) == N:
        tmp = 0
        for q in query:
            a, b, c, d = q

            if A[b - 1] - A[a - 1] == c:
                tmp += d
        res = max(res, tmp)
        return

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


for i in range(1, M + 1):
    solve([i])
print(res)

Submission status: Accepted

Solution code:
def solve():
    N,M,Q = map(int,input().split())
    global info
    info = []
    for _ in range(Q):
        a,b,c,d = map(int,input().split())
        a -= 1
        b -= 1
        info.append([a,b,c,d])

    print(dfs(list(),M,N))

def dfs(A,M,N):
    if len(A) == N:
        return calcPoint(A)
    
    res = 0
    prev = A[-1] if len(A) > 0 else 1
    for i in range(prev,M+1):
        A.append(i)
        res = max(res,dfs(A,M,N))
        A.pop()
    
    return res

def calcPoint(A):
    result = 0
    for a,b,c,d in info:
        if A[b] - A[a] == c:
            result += d
    return result
                
if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

ans = 0
for A in com:
    tmp = 0
    for a,b,c,d in qs:
        if (A[b-1] - A[a-1] == c): tmp += d
    ans = max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m,q=(int(x) for x in input().split())

i = itertools.combinations_with_replacement(range(1,m+1),n)
score = 0
a,b,c,d = [0]*q,[0]*q,[0]*q,[0]*q
for j in range(q):
    a[j],b[j],c[j],d[j]=(int(x) for x in input().split())
for array in i:
    tmp = 0
    for j in range(q):
        tmp += d[j] if array[b[j]-1] - array[a[j]-1] == c[j] else 0
    score = max(tmp,score)
print(score)

Submission status: Accepted

Solution code:
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)

def dfs(A):
    if len(A) == n:  # 数列が完成している場合
        score = 0
        for i in range(q):
            if A[b[i]-1] - A[a[i]-1] == c[i]:
                score += d[i]
        return score

    ans = 0
    for i in range(A[-1], m+1):
        A.append(i)
        ans = max(ans, dfs(A))
        A.pop()
    return ans

print(dfs([1]))

Submission status: Accepted

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

a_list = []

def dfs(n, m, l):
    a = copy.copy(l)
    if a.count(0) == 0:
        a_list.append(a)
        return
    if a[0] == 0:
        for i in range(1, n+1):
            a[0] = i
            dfs(n, m, a)
        return
    for i in range(1, n):
        if a[i] == 0:
            for j in range(m-a[i-1]+1):
                a[i] = a[i-1] + j
                dfs(n, m, a)
            return

def get_score(l, score_list):
    score = 0
    for s in score_list:
        a = s[0]
        b = s[1]
        c = s[2]
        d = s[3]
        if l[b-1] - l[a-1] == c:
            score += d
    return score
dfs(n, m, [0 for _ in range(n)])
# print(a_list)
ans_list = [get_score(a, score_list) for a in a_list]
print(max(ans_list))

Submission status: Accepted

Solution code:
import itertools

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

number = []
for i in range(m):
    number.append(i+1)
a = list(itertools.combinations_with_replacement(number,n))
length = len(a)
memo = [0] * length
ans = 0

for i in range(length):#組み合わせの数回す
    sum = 0
    for j in range(q):
       if a[i][num[j][1]-1] - a[i][num[j][0]-1]  == num[j][2]:
            sum += num[j][3]
    ans = max(sum,ans)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import combinations_with_replacement

n, m, q = map(int, input().split())
abcd = [0] * q
for i in range(q):
    abcd[i] = list(map(int, input().split()))
# print(0)
# comb = [1] * n + [0] * (m - 1)
# combination_all = set(itertools.permutations(comb))  # 5!通り出力する
cmb = combinations_with_replacement([i for i in range(1, m + 1)], n)
all_array = list(cmb)
"""for i in combination_all:
    tmp = 1
    lis = []
    for j in range(len(i)):
        if i[j]:
            lis.append(tmp)
        else:
            tmp += 1
    all_array.append(lis)"""
# print(all_array)
ans = 0  # maxをとる
for arr in all_array:
    val = 0
    for j in range(q):
        if arr[abcd[j][1] - 1] - arr[abcd[j][0] - 1] == abcd[j][2]:
            val += abcd[j][3]
    ans = max(ans, val)
print(ans)
# bit 全探索で i が成り立つと仮定する
# 連結する奴の中で最大と最小の差がN-1以下なら成立
"""ans = 0

for i in range(2**n):
    score = 0
    emerge = []
    lis = []
    for j in range(n):
        if i>>j & j:
            if a[i] in emerge:"""

Submission status: Accepted

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

Submission status: Accepted

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

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

ans = [0]
def dfs(x,n2,m1):
  if len(x) == n2:
    score = sum(x1[3] for x1 in list1 if x[x1[1]-1]-x[x1[0]-1] == x1[2])
    if score > ans[0]:
      ans[0] = score
  else:
    for i in range(1,m1+1,1):
      if i >= x[-1]:
        dfs(x+[i],n2,m1)

dfs([1],N,M)
print(ans[0])

Submission status: Accepted

Solution code:
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-1)
    b.append(bi-1)
    c.append(ci)
    d.append(di)

def score(A):
    tmp = 0
    for j in range(Q):
        if A[b[j]] - A[a[j]] == c[j]:
            tmp += d[j]
    return tmp
    
def dfs(A):
    if len(A) == N:
        return score(A)
    Alast = A[-1] if len(A) > 0 else 1
    res = 0
    for k in range(Alast,M+1):  
        A.append(k)
        res = max(res,dfs(A))
        A.pop()
    return res

print(dfs([]))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,m,q = LI()
    aa = [LI() for _ in range(q)]
    r = 0
    for l in itertools.combinations_with_replacement(range(1,m+1), n):
        t = 0
        for a,b,c,d in aa:
            if l[b-1] - l[a-1] == c:
                t += d
        if r < t:
            r = t
    return r

print(main())

Submission status: Accepted

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

ans=0
def search(l):
    global ans
    if len(l)==n+1:
        score=0
        for i in range(q):
            if l[a[i][1]]-l[a[i][0]]==a[i][2]:
                score+=a[i][3]
        ans=max(ans,score)
    
    else:
        for i in range(l[-1],m+1):
            search(l+[i])

search([1])

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import itertools
N, M, Q = map(int,input().split())
L = list(itertools.combinations_with_replacement(range(1, M + 1), N))
D = []
for i in range(Q):
    D.append(list(map(int,input().split())))

#print(l)
#全てのA

ans = 0
for A in L:
    tmp = 0
    for i in range(Q):
        a = D[i][0]
        b = D[i][1]
        c = D[i][2]
        d = D[i][3]
        if A[b-1] - A[a-1] == c:
            tmp += d
        
        ans = max(ans,tmp)

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

def dfs(a):
    if len(a)==n:
        tmp=a[:]
        a_lis.append(tmp)
        return
    
    for i in range(m):
        if len(a)>0 and i<a[-1]:
            continue
        a.append(i)
        dfs(a)
        a.pop()

cnt=0        
n,m,q=map(int,input().split())
lis=[[int(i) for i in input().split()]for i in range(q)]
a_lis=[]

dfs([])
ans=0
for i in a_lis:
    score=0
    for a,b,c,d in lis:
        if i[b-1]-i[a-1]==c:
            score+=d
    ans=max(ans,score)
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)]
sumlist=[]
for A in itertools.combinations_with_replacement(range(1,m+1),n):
  sum=0
  for a,b,c,d in abcd:
    if A[b-1]-A[a-1]==c:
      sum+=d
    sumlist.append(sum)
print(max(sumlist))

Submission status: Accepted

Solution code:
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])

from itertools import combinations

a = [i for i in range(1, n+m+1)]
As = list(combinations(a, n))
ans = []

for a in As:
    A = []
    now = 0
    for i in range(1, n+m+1):
        if i in a:
            A.append(now)
        else:
            now += 1
    if A[0] == 0:
        continue
    D = 0
    for abc in abcd:
        if A[abc[1]] - A[abc[0]] == abc[2]:
            D += abc[3]
    ans.append(D)
print(max(ans))

Submission status: Accepted

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

ans = 0

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

def dfs(A):
  global ans

  if len(A) == n:
    score = calc(A)
    ans = max(ans, score)

  elif len(A) == 0:
    for i in range(1, m+1):
      dfs([i])

  else:
    for i in range(A[-1], m+1):
      dfs(A + [i])

dfs([])
print(ans)

Submission status: Accepted

Solution code:
nums = [int(e) for e in input().split()]
n = nums[0]
m = nums[1]
q = nums[2]

max_score = 0

total_qs = []

for i in range(q):
    qs = [int(e) for e in input().split()]
    total_qs += [qs]


# 数列の得点計算
def calc_score(a2):
    score = 0

    for tmp_q in total_qs:
        if a2[tmp_q[1]] - a2[tmp_q[0]] == tmp_q[2]:
            score += tmp_q[3]

    return score


# Aの数列を全部くみ上げる
# 再起関数
# DFS(深さ優先探索)
def dfs(a1):
    global max_score
    if len(a1) == n+1:
        # calc score
        tmp_score = calc_score(a1)
        if max_score < tmp_score:
            max_score = tmp_score
        return

    a1.append(a[len(a1) - 1])
    while a1[len(a1) - 1] <= m:
        dfs(a1)
        a1[len(a1) - 1] += 1

    a1.pop(-1)
    return


# ただの数え上げ用の1
# 実際の配列ではない
a = [1]

dfs(a)

print(max_score)

Submission status: Accepted

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

ans = 0
for A in itertools.combinations_with_replacement(range(1,M+1),N):
    cnt = 0
    for q in range(Q):
        if A[abcd[q][1] - 1] - A[abcd[q][0] - 1] == abcd[q][2]:
            cnt += abcd[q][3]
    ans = max(ans,cnt)

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())
import itertools
ans=0
for A in itertools.combinations_with_replacement(range(1,M+1),N):
  A_=list(A)
  s=0
  
  for i in range(Q):
    if A_[b[i]-1]-A_[a[i]-1]==c[i]:
      s+=d[i]
    ans=max(ans,s)
print(ans)

Submission status: Accepted

Solution code:
# 点数は必ずdの組み合わせになる
# 点数を決め売ったときに数列が妥当か決定できる？
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
from itertools import combinations_with_replacement

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
req = [list(map(int, input().split())) for i in range(Q)]
maxi = 0
def dfs(A):
  global maxi
  
  if len(A) == N:  # 終端条件 --- 10 重ループまで回したら処理して打ち切り
    ans = 0
    for i in range(Q):
      if A[req[i][1]-1] - A[req[i][0]-1] == req[i][2]:
        ans += req[i][3]
        
    maxi = max(maxi, ans)
    return
      
  if len(A) == 0:
    for v in range(1, M+1):
      A.append(v)
      dfs(A)
      A.pop()
      
  else:    
    for v in range(A[-1], M+1):
      A.append(v)
      dfs(A)
      A.pop() # これが結構ポイント

dfs([])
print(maxi)

Submission status: Accepted

Solution code:
import itertools
n,m,q = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(q)]
ans = 0
list_ = list(itertools.combinations_with_replacement(range(1, m + 1), n))
for i in list_:
    tmp = 0
    for a,b,c,d in arr:
        if (i[b-1] - i[a-1]==c):
            tmp+=d
    ans=max(ans,tmp)
print(ans)

Submission status: Accepted

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

ans = []

# 単調増加考慮
def dfs(l):
    if len(l) == N:
        tmp = 0
        for q in query:
            if (l[q[1]-1] - l[q[0]-1]) == q[2]:
                tmp += q[3]
        ans.append(tmp)
        return
    prev = l[-1] if len(l) > 0 else 1
    for v in range(prev, M+1):
        l.append(v)
        dfs(l)
        l.pop()


dfs([])
print(max(ans))

Submission status: Accepted

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

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

def dfs(a):
    if len(a)==n:
        return point(a)
    res = 0
    prev_last = a[-1] if len(a) > 0 else 1
    for i in range(prev_last, m+1):
        a.append(i)
        res = max(res, dfs(a))
        a.pop()
    return res

print(dfs([]))

Submission status: Accepted

Solution code:
import itertools
n, m, q = map(int, input().split())
A = itertools.combinations_with_replacement(range(1, m+1), n)
quads = [[int(i) for i in input().split()] for j in range(q)]
max_p = 0
for a in A:
    p = 0
    for quad in quads:
        if a[quad[1] - 1] - a[quad[0] - 1] == quad[2]:
            p += quad[3]
    if max_p < p:
        max_p = p
print(max_p)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
def calc(a, n, m, arr):
    if len(a) == n:
        val = 0
        for p, q, c, d in arr:
            if a[p-1] + c == a[q-1]:
                val += d
        return val
    else:
        val = 0
        for i in range(a[-1], m+1):
            a.append(i)
            val = max(val, calc(a, n, m, arr))
            a.pop(-1)
        return val

def main():
    n, m, q = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(q)]
    a = [1]
    print(calc(a, n, m, arr))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# https://www.youtube.com/watch?v=C5_NnCp1CRI&feature=youtu.be

import sys
# sys.stdin = open('input.txt')
import itertools

# C++
# https://atcoder.jp/contests/abc165/submissions/12656990
# Python
# https://atcoder.jp/contests/abc165/submissions/12832942
# https://atcoder.jp/contests/abc165/submissions/12832027
def dfs(A):
    """
    dfs([1]) で使用。index 1 からが本来求めたい数列になる
    """
    global ans
    if len(A) == n+1:
        # print(A)
        now = 0
        for j in range(q):
            if A[b[j]] - A[a[j]] == c[j]:
                now += d[j]
        ans = max(ans, now)
        return
    else:
        # 以下 2 行いずれの場合も、既存リストが mutate されるのでうまく再帰できない
        # A.append(A[-1])
        # A += [A[-1]]
        # 以下は変数の再定義なのでリストは mutate されない
        A = A + [A[-1]]
        # こちらも mutate しない例
        # A = A[:]
        # A.append(A[-1])
        while A[-1] <= m:
            # print(A)
            dfs(A)
            A[-1] += 1

# https://atcoder.jp/contests/abc165/submissions/12679398
# AC
def dfs2(i):
    global ans
    for j in range(num[i-1], m):
        num[i] = j
        if i == n:
            print(num)
            now = 0
            for k in range(q):
                if num[b[k]] - num[a[k]] == c[k]:
                    now += d[k]
            ans = max(ans, now)
        else:
            dfs2(i+1)

def solve_combinations_with_replacement(n, m):
    def update_ans(A):
        global ans
        now = 0
        for j in range(q):
            if A[b[j]-1] - A[a[j]-1] == c[j]:
                now += d[j]
        ans = max(ans, now)
        return

    global ans
    it = [i for i in range(m)]
    for A in itertools.combinations_with_replacement(it, n):
        update_ans(A)


n, m, q = map(int, input().split())
a, b, c, d = [], [], [], []
ans = 0

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)

dfs([1])

# num = [0] * (n+1)
# dfs2(1)

# solve_combinations_with_replacement(n, m)

print(ans)

Submission status: Accepted

Solution code:
# https://www.youtube.com/watch?v=C5_NnCp1CRI&feature=youtu.be
# TODO: combinations_with_replacement in Python
# https://atcoder.jp/contests/abc165/submissions/12656990

# TODO: WA
import sys
# sys.stdin = open('input.txt')


# https://atcoder.jp/contests/abc165/submissions/12832942
def dfs(A):
    global ans
    if len(A) == n+1:
        now = 0
        for j in range(q):
            if A[b[j]] - A[a[j]] == c[j]:
                now += d[j]
        ans = max(ans, now)
        return
    else:
        # A.append(A[-1])
        A = A + [A[-1]]
        while A[-1] <= m:
            # print(A)
            dfs(A)
            A[-1] += 1

def dfs_no_mutation(original):
    global ans
    A = original[:]
    if len(A) == n+1:
        now = 0
        for j in range(q):
            if A[b[j]] - A[a[j]] == c[j]:
                now += d[j]
        ans = max(ans, now)
        return
    else:
        A.append(A[-1])
        while A[-1] <= m:
            print(A)
            dfs(A)
            A[-1] += 1


def comb_with_replacement(A, n, m):
    global lists
    if len(A) == n+1:
        lists.append(A)
    else:
        A.append(A[-1])
        while A[-1] <= m:
            comb_with_replacement(A, n, m)
            A[-1] += 1

# https://atcoder.jp/contests/abc165/submissions/12679398
# AC
def dfs2(i):
    global ans
    for j in range(num[i-1], m):
        num[i] = j
        if i == n:
            print(num)
            now = 0
            for k in range(q):
                if num[b[k]] - num[a[k]] == c[k]:
                    now += d[k]
            ans = max(ans, now)
        else:
            dfs2(i+1)


n, m, q = map(int, input().split())
a, b, c, d = [], [], [], []
ans = 0

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)

dfs([1])
# dfs_no_mutation([1])

num = [0] * (n+1)
# dfs2(1)

# lists = []
# comb_with_replacement([1], 4, 5)
# print(lists)
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations_with_replacement
input = sys.stdin.readline
 
 
def readstr():
    return input().strip()
 
 
def readint():
    return int(input())
 
 
def readnums():
    return map(int, input().split())
 
 
def readstrs():
    return input().split()
 
 
N, M, Q = readnums()
num_list = [list(readnums()) for _ in range(Q)]
 
ans = 0
for v in combinations_with_replacement(range(1, M + 1), N):
    val = 0
    for n in num_list:
        if v[n[1] - 1] - v[n[0] - 1] == n[2]:
            val += n[3]
    ans = max(ans, val)
 
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)]

# 重複組み合わせ: nHr = n+r-1Cr を考える
ans = 0
R = [i for i in range(1, M+1)]
# print(R)

for comb in itertools.combinations_with_replacement(R, N):
    temp = 0
    for abcd in ABCD:
        a, b, c, d = abcd
        if comb[b-1] - comb[a-1] == c:
            temp += d
    if temp >= ans:
        ans = temp

    # print("comb: {}, temp: {}, ans: {}".format(comb, temp, ans))

print(ans)