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

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

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

    maxScore = 0
    for combination in combinations:
        score = 0
        for a, b, c, d in abcds:
            if combination[b-1] - combination[a-1] == c:
                score += d
        if score >= maxScore:
            maxScore = score

    print(maxScore)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
inpl = lambda: tuple(map(int,input().split()))
N, M, Q = inpl()
abcd = []
for _ in range(Q):
    a, b, c, d = inpl()
    abcd.append((a-1,b-1,c,d))

ans = 0
pool = [(0,0)]
A = []
while pool:
    d, m = pool.pop()
    while len(A) > d:
        A.pop()
    A.append(m)
    if d == N-1:
        point = sum(d for a, b, c, d in abcd if A[b]-A[a] == c)
        if point > ans:
            ans = point
    else:
        for k in range(m,M):
            pool.append((d+1,k))
print(ans)

Submission status: Accepted

Solution code:
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

import itertools
n,m,q=n1()
s=n3(q)

s=sorted(s, key=lambda x: x[3],reverse=True)

Alist=list(itertools.combinations_with_replacement(range(1,m+1), n))
ans=0
for A in Alist:
    tmp=0
    for r in s:
        if A[r[1]-1]-A[r[0]-1]==r[2]:
            tmp+=r[3]
    ans=max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

ans=0
y=[i for i in range(m)]
for v in itertools.combinations_with_replacement(y,n):
    cnt=0
    for a,b,c,d in x:
        a-=1
        b-=1
        if v[b]-v[a]==c:
            cnt+=d
    ans=max(cnt,ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
N,M,Q = map(int ,input().split())
ls = [0]*Q
for i in range(Q):
  a,b,c,d = map(int, input().split())
  ls[i] = (a,b,c,d)
def f(l,cnt):
  if cnt>0:
    j = l[-1]
    ans  = 0
    for i in range(j,M+1):
      ans = max(f(l+[i],cnt-1),ans)
    return ans
  else:
    m  = 0
    for a,b,c,d in ls:
      if l[b-1]-l[a-1]==c:
        m += d
    return m
ans  = 0
for i in range(1,M+1):
  ans = max(ans,f([i],N-1))
print(ans)

Submission status: Accepted

Solution code:
def main():
    n,m,q = map(int,input().split())

    l = [list(map(int,input().split())) for i in range(q)]
    ans = 0

    def count(a):
        score = 0
        for i in range(q):
            if a[l[i][1]-1] - a[l[i][0]-1] == l[i][2]:
                score += l[i][3]
        return score

    def dfs(x,now,s):
        if x == n:
            return count(s)
        score = 0
        for i in range(now,m+1):
            s.append(i)
            score = max(score,dfs(x+1,i,s))
            s.pop()
        return score
    print(dfs(0,1,[]))

if __name__ =="__main__":
    main()

Submission status: Accepted

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

import itertools

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

answer_candeidates = list(itertools.combinations_with_replacement(candidateA,N))
#print(answer_candeidates)
ans = 0
for answer_candeidate in answer_candeidates:
    tmp_answer = 0
    for abcd in ABCD_list:
        t = answer_candeidate[abcd[1]-1] - answer_candeidate[abcd[0]-1]
        #print(t)
        if t == abcd[2]:
            tmp_answer += abcd[3]
            #print(tmp_answer)
    ans = max(tmp_answer,ans)

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

def gen(mae):
    global A_cand
    if len(mae)==N:
        A_cand.append(mae)
        return 0
    for one in range(mae[-1], M+1):
        gen(mae+[one])
for i in range(1,M+1):
    gen([i])
for one in A_cand:
    score = 0
    for i in range(Q):
        a,b,c,d = abcd[i]
        if one[b-1]-one[a-1]==c:
            score+=d
    max_score = max(score, max_score)
print(max_score)

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
l=[list(map(int,input().split())) for i in range(q)]
L=[]
for i in range(1,m+1):
  if n==1:
    L.append((i))
  else:
    for i2 in range(i,m+1):
      if n==2:
        L.append((i,i2))
      else:
        for i3 in range(i2,m+1):
          if n==3:
            L.append((i,i2,i3))
          else:
            for i4 in range(i3,m+1):
              if n==4:
                L.append((i,i2,i3,i4))
              else:
                for i5 in range(i4,m+1):
                  if n==5:
                    L.append((i,i2,i3,i4,i5))
                  else:
                    for i6 in range(i5,m+1):
                      if n==6:
                        L.append((i,i2,i3,i4,i5,i6))
                      else:
                        for i7 in range(i6,m+1):
                          if n==7:
                            L.append((i,i2,i3,i4,i5,i6,i7))
                          else:
                            for i8 in range(i7,m+1):
                              if n==8:
                                L.append((i,i2,i3,i4,i5,i6,i7,i8))
                              else:
                                for i9 in range(i8,m+1):
                                  if n==9:
                                    L.append((i,i2,i3,i4,i5,i6,i7,i8,i9))
                                  else:
                                    for i10 in range(i9,m+1):
                                      L.append((i,i2,i3,i4,i5,i6,i7,i8,i9,i10))
ans=[]
for i in range(len(L)):
  ct=0
  for j in range(q):
    if L[i][l[j][1]-1]-L[i][l[j][0]-1]==l[j][2]:
      ct+=l[j][3]
  ans.append(ct)
print(max(ans))

Submission status: Accepted

Solution code:
def main():
    N, M, Q = map(int, input().split())
    items = []

    for i in range(Q):
        items.append(tuple(map(int, input().split())))

    # print(items)

    def list_a(a: list):
        if len(a) == N:
            return [a]
        else:
            arr = []
            if len(a) == 0:
                last = 1
            else:
                last = a[-1]

            for i in range(last, M + 1):
                arr += list_a(a + [i])
            return arr

    candidates = list_a([])
    # print(candidates)

    max_score = -100
    max_A = None

    for A in candidates:
        score = 0
        for a, b, c, d in items:
            if A[b-1] - A[a-1] == c:
                score += d

        if score > max_score:
            max_score = score
            max_A = A

    print(max_score)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
e=[]
for i in range(q):
    a,b,c,d=map(int,input().split())
    e.append([a,b,c,d])
def calc(a):
    #print(a)
    an=0
    for i in range(q):
        if a[e[i][1]-1]-a[e[i][0]-1]==e[i][2]:
            an+=e[i][3]
    return an
ans=[]
def ca(a,i,n,prev):
    if i==n:
        ans.append(calc(a))
    else:
        for j in range(prev,m+1):
            a[i]=j
            ca(a,i+1,n,j)

a=[0]*n 
ca(a,0,n,1)
print(max(ans))

Submission status: Accepted

Solution code:
# C - Many Requirements

import itertools

N, M, Q = map(int, input().split())
TEST = [0] * Q
for i in range(Q):
    TEST[i] = list(int(x) for x in input().split())

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

ans = 0
for l in list(itertools.combinations_with_replacement(nums, N)):
    tmp = 0
    for t in TEST:
        if l[t[1]-1]-l[t[0]-1] ==t[2]:
            tmp += t[3]
        else:
            continue
    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
ans=-float("INF")
l=[list(map(int,input().split())) for i in range(q)]
from itertools import combinations_with_replacement as pe
for i in pe(range(m),r=n):
    p=0
    for x,y,di,po in l:
        if i[y-1]-i[x-1]==di:p+=po
    ans=max(p,ans)
print(ans)

Submission status: Accepted

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


def gen_a(m, n):
    if n == 1:
        return {(i,) for i in range(1, m + 1)}
    else:
        bef_a = gen_a(m, n - 1)
        ret = set()
        for bef in bef_a:
            for i in range(bef[-1], m + 1):
                ret.add(bef + (i,))
        return ret


ans = 0
for a_tuple in gen_a(m, n):
    score_a = 0
    for a, b, c, d in score:
        a, b = a - 1, b - 1
        if a_tuple[b] - a_tuple[a] == c:
            score_a += d
    ans = max(score_a, ans)

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

N, M, Q = [int(x) for x in input().split()]
ABCD = [[int(x) for x in input().split()] for i in range(Q)]

best = 0
for combo in combinations_with_replacement(range(1, M + 1), r=N):
    score = 0
    for a, b, c, d in ABCD:
        assert 1 <= a < b <= N
        assert 0 <= c <= M - 1
        if combo[b - 1] - combo[a - 1] == c:
            score += d
    best = max(best, score)
print(best)

Submission status: Accepted

Solution code:
import itertools

n,m,q=map(int,input().split())
num=[int(i) for i in range(1,m+1)]
x=[]
for i in range(q):
    a,b,c,d=map(int,input().split())
    a,b=a-1,b-1
    x.append([a,b,c,d])
ans=0
for i in itertools.combinations_with_replacement(num,n):
    s=0
    for j in x:
        if i[j[1]]-i[j[0]]==j[2]:
            s+=j[3]
    ans=max(ans,s)
print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m,q = map(int,input().split())
num = [i for i in range(1,m+1)]
l = []
for i in range(q):
    r = list(map(int,input().split()))
    l.append(r)
l.sort()
stock = list(itertools.combinations_with_replacement(num, n))
ans = 0
for i in stock:
    s = 0
    for j in l:
        if i[j[1]-1] - i[j[0]-1] == j[2]:
            s += j[3]
            #print(s)
        #print(i[j[1]-1] - i[j[0]-1])
    if ans < s:
        ans = s
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

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

for _ in range(Q):
    x, y, z, w = map(int, input().split(' '))
    a.append(x)
    b.append(y)
    c.append(z)
    d.append(w)

max_score = 0

for A in combinations_with_replacement(range(1, M + 1), r=N):
    A = [None, *A]
    score = 0
    for i in range(1, Q + 1):
        if A[b[i]] - A[a[i]] == c[i]:
            score += d[i]
    max_score = max(score, max_score)

print(max_score)

Submission status: Accepted

Solution code:
from itertools import combinations
n, m, q = map(int, input().split())
abcd = []
for _ in range(q):
    a, b, c, d = map(int, input().split())
    abcd.append((a, b, c, d))

ans = 0
for i in combinations(list(range(1,n+m)), m-1):
    tmp = 1
    li = []
    for j in range(1, n+m):
        if j in i:
            tmp += 1
        else:
            li.append(tmp)
    score = 0
    for a, b, c, d in abcd:
        if li[b-1]-li[a-1]==c:
            score += d
    ans = max(ans, score)
print(ans)

Submission status: Accepted

Solution code:
def point(A, queries):
    ans = 0
    for query in queries:
        a, b, c, d = query
        if A[b - 1] - A[a - 1] == c:
            ans += d
    return ans

def next(A, M):
    for n in range(N):
        if A[N - n - 1] < M:
            A = A[:N - n - 1] + [A[N - n - 1] + 1] * (n + 1)
            return A
    return []



N, M, Q = map(int, input().split())
queries = [[int(i) for i in input().split()] for q in range(Q)]
A = [1] * N
ans = 0
while True:
    ans = max(ans, point(A, queries))
    A = next(A, M)
    if A == []:
        break
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,m,q = map(int,input().split())
x = [list(map(int,input().split()))for i in range(q)]
ans = 0
def calc(l):
    res = 0
    
    for i in range(q):
        a,b,c,d = x[i][0],x[i][1],x[i][2],x[i][3]
        a -= 1
        b -= 1
        if l[b] - l[a] == c:res += d
    return res
def dfs(d,nums):
    if d == n:
        
        return calc(nums)
    res = 0
    for i in range(1,m+1):
        if len(nums) > 0 and nums[-1] > i:continue
        res = max(res,dfs(d+1,nums + [i]))
    return res

ans = dfs(0,[])
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)]

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

numbers = list(itertools.combinations_with_replacement(numbers, n))


ans = 0
tmp = 0

for i in range(len(numbers)):
    s = numbers[i]
    tmp = 0
    
    for j in range(q):
        if s[li[j][1]-1] - s[li[j][0]-1] == li[j][2]:
            tmp += li[j][3]
    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
cin = open(0).read().strip().split('\n')
n, m, q = map(int, cin[0].split(' '))
abcd = [tuple(map(int, a.split(' '))) for a in cin[1:]]

ret = 0
import itertools
for case in itertools.combinations_with_replacement(list(range(1,m+1)), n):
    tmp = 0
    for c in abcd:
        if case[c[1]-1] - case[c[0]-1] == c[2]:
            tmp += c[3]
    ret = max(ret, tmp)
print(ret)

Submission status: Accepted

Solution code:
from collections import deque
import copy

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

abcd = []
for _ in range(Q):
    a,b,c,d = map(int,input().split())
    abcd.append((a,b,c,d))
    
q = deque([[1]])
for _ in range(N):
    ap = deque([])
    while q:
        p = q.pop()
        num = p[-1]
        for i in range(num,M+1):
            new_list = p+[i]
            ap.append(new_list)
    q = ap
    
ans = 0
for x in q:
    ret = 0
    for a,b,c,d in abcd:
        if x[b]-x[a] == c:
            ret += d
    ans = max(ans,ret)
    
print(ans)

Submission status: Accepted

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

def solve(N: int, M: int, Q: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
    result = 0
    for iter in itertools.combinations_with_replacement(range(1,M+1),N):
        l = sorted(list(iter))
        sum = 0
        for i in range(Q):
            if l[b[i]-1] - l[a[i]-1] == c[i]:
                sum += d[i]
        result = max(result,sum)
    print(result)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
import itertools
N, M, Q = map(int, input().split())
Qs = [list(map(int, input().split())) for _ in range(Q)]

_max = 0
for A in itertools.combinations_with_replacement(range(1, M+1), N):
    score = sum([q[3] for q in Qs if A[q[1] - 1] - A[q[0] - 1] == q[2]])
    _max = score if _max < score else _max
print(_max)

Submission status: Accepted

Solution code:
from itertools import combinations


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

    res_max = 0

    # 0-1
    a_list = [0] * n
    for com in combinations(range(n + m - 1), n):

        for i, c in enumerate(com):
            if i == 0:
                a_list[i] = c + 1
            else:
                a_list[i] = a_list[i - 1] + c - com[i - 1] - 1
        # print(a_list)
        res = 0
        for i in range(q):
            a, b, c, d = q_list[i]
            if a_list[b - 1] - a_list[a - 1] == c:
                res += d

        if res > res_max:
            res_max = res
    # print(res_max)
    return res_max


def main():
    n, m, q = map(int, input().split())
    q_list = [list(map(int, input().split())) for _ in range(q)]
    res = solve(n, m, q, q_list)
    print(res)


def test():
    assert solve(3, 4, 3, [[1, 3, 3, 100], [1, 2, 2, 10], [2, 3, 2, 10]]) == 110
    assert solve(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]
    ]) == 357500
    assert solve(10, 10, 1, [[1, 10, 9, 1]]) == 1


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

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

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

import itertools

ans = {}

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

Submission status: Accepted

Solution code:
import sys
import math


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


def calc(k, A, n, m, Q):
    if k == n:
        s = score(A, Q)
        return s

    start = 1
    if k >= 1:
        start = A[k - 1]

    res = 0
    for i in range(start, m + 1):
        A[k] = i
        res = max(res, calc(k + 1, A, n, m, Q))

    return res


def main():
    input = sys.stdin.readline

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

    A = [1 for i in range(n)]
    res = calc(0, A, n, m, Q)

    print(res)


main()

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

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

ans = 0
for comb in combinations_with_replacement(range(1, M+1), N):
    score = 0
    for a, b, c, d in query:
        if comb[b-1] - comb[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())
suuji = [i for i in range(1,M+1)]
L = []
for i in range(Q):
  temp = list(map(int,input().split()))
  L.append(temp)

#print(suuji)

Aall = list(itertools.combinations_with_replacement(suuji, N))
#print(Aall)

ans = 0
for A in Aall:
  test = 0
  for i in range(Q): #Q組のセットで確認 L[i]という数列が四つの数の組
    #print(L[i])
    #print(A)
    if A[L[i][1]-1]-A[L[i][0]-1] == L[i][2]:
      test += L[i][3]
  ans = max(ans,test)
print(ans)

Submission status: Accepted

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

l = []
for i in range(q):
  a,b,c,d = map(int, input().split())
  l.append((a,b,c,d))
  
comb = itertools.combinations_with_replacement(range(1,m+1), n)

max_score = 0
for e in comb:
  score = 0
  for j in l:
    if e[j[1]-1]-e[j[0]-1]==j[2]:
      
      score += j[3]
  if score > max_score:
    max_score = score
print(max_score)

Submission status: Accepted

Solution code:
import itertools
n, m, q = map(int, input().split())
a = []
b = []
c = []
d = []
for i in range(q):
    abcd=list(map(int, input().split()))
    a.append(abcd[0])
    b.append(abcd[1])
    c.append(abcd[2])
    d.append(abcd[3])
one_to_m = [i+1 for i in range(m)]
A = list(map(list, list(itertools.combinations_with_replacement(one_to_m, n))))
maximum = 0
for line in A:
    score = 0
    for i in range(q):
        if c[i] == line[b[i]-1] - line[a[i]-1]:
            score += d[i]
    if maximum < score:
        maximum = score
print(maximum)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
from collections import deque

def main():
    N, M, Q = map(int, readline().rstrip().split())
    P = [tuple(map(int, readline().rstrip().split())) for _ in range(Q)]
    ans = 0
    l = [[i] for i in range(1, M+1)]
    que = deque(l)
    for i in range(N):
        for _ in range(len(que)):
            ll = que.popleft()
            for j in range(ll[-1], M+1):
                que.append(ll + [j])
    
    for pair in que:
        score = 0
        for a, b, c, d in P:
            if pair[b-1] - pair[a-1] == c:
                score += d
        ans = max(ans, score)
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m, q = map(int, input().split())
a, b, c, d = [], [], [], []
for i in range(q):
	x, y, z, w = map(int, input().split())
	x, y = x - 1, y - 1
	a.append(x)
	b.append(y)
	c.append(z)
	d.append(w)

import itertools
lst = list(range(1, m + 1)) #[1,2,...,m]
A = list(itertools.combinations_with_replacement(lst, n))

maxs = 0
for v in A:
	score = 0
	for i in range(q):
		if v[b[i]] - v[a[i]] == c[i]:
			score += d[i]
	maxs = max(maxs, score)

print(maxs)

Submission status: Accepted

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

m = M - 1

def f(s):
    if len(s) == N:
        return [s]
    result = []
    if s == '':
        r = 0
    else:
        r = int(s[-1])
    for i in range(r, m + 1):
        result.extend(f(s + str(i)))
    return result

result = 0
V = f('')
for s in V:
    A = [int(c) + 1 for c in s]
    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:
import itertools


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

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

row = list(itertools.combinations_with_replacement(num, N))

point_max = 0
for i in range(len(row)):
    r = list(row[i])
    point = 0
    for j in range(Q):
        a = int_list[j][0]
        b = int_list[j][1]
        c = int_list[j][2]
        d = int_list[j][3]
        if r[b-1] - r[a-1] == c:
            point += d
    point_max = max(point, point_max)

print(point_max)

Submission status: Accepted

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

def calc(ar, s):
    if len(ar) == n:
        if s <= m: candi.append(ar)
        return
    max_num = ar[len(ar) - 1]
    for i in range(0, m-s+1):
        tmp = copy.deepcopy(ar)
        tmp.append(max_num+i)
        calc(tmp, s+i)

calc([1], 1)
tes = [list(map(int, input().split())) for _ in range(q)]
ans = 0

for now in candi:
    tmp = 0
    for cons in tes:
        a, b, c, d = cons[0], cons[1], cons[2], cons[3]
        if now[b-1] - now[a-1] == c: tmp += d
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
N, M, Q = [int(n) for n in 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] = [int(n) for n in input().split()]

def gen(i, n, m):
    if n == 0:
        yield []
        return
    for f in range(i, m + 1):
        for rest in gen(f, n - 1, m):
            yield [f] + rest

sm = 0
for A in gen(1,N,M):
    s = 0
    for i in range(Q):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            s += d[i]
    if s > sm:
        sm = s

print(sm)

Submission status: Accepted

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

A_list = [[1, i] for i in range(1, M+1)]
for i in range(2, N):
  t_list = []
  for e in A_list:
    for j in range(e[-1], M+1):
      t_list.append(e + [j])
  A_list = t_list

# print(A_list)

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

print(ans)

Submission status: Accepted

Solution code:
import collections
def main():

    N, M, Q = map(int, input().split())
    p = collections.defaultdict(int)
    for _ in range(Q):
        a, b, c, d = map(int, input().split())
        p[(a-1, b-1, c)] = d

    lv = [[1]]
    for i in range(N):
        temp = []
        for v in lv:
            for j in range(v[-1], M+1):
                temp.append(v + [j])
        lv = temp

    ans = 0
    for v in lv:
        q = 0
        for a, b, c in p:
            if v[b] - v[a] == c:
                q += p[(a, b, c)]
        ans = max(ans, q)
    return ans

if __name__ == '__main__':
    print(main())

Submission status: Accepted

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


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


for num in li:
    p = 0
    for point in points:
        if num[point[1] - 1] - num[point[0] - 1] == point[2]:
            p += point[3]
    ans = max(p, ans)


print(ans)

Submission status: Accepted

Solution code:
def resolve():
    import itertools
    n, m, q = map(int, input().split())
    cond = [list(map(int, input().split())) for _ in range(q)]
    pos = list(itertools.combinations_with_replacement(range(1, m+1), n))
    ans = 0
    for i in range(len(pos)):
        test = list(pos[i])
        point = 0
        for j in range(q):
            if test[cond[j][1]-1] - test[cond[j][0]-1] == cond[j][2]:
                point += cond[j][3]
        ans = max(ans, point)
    print(ans)
resolve()

Submission status: Accepted

Solution code:
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 - 1)
    B.append(b - 1)
    C.append(c)
    D.append(d)

L = []

def f(l):
    if len(l) == n:
        L.append(l)
        return
    for i in range(l[-1], m + 1):
        f(l + [i])

for i in range(1, m + 1):
    f([i])

ans = 0

for l in L:
    ans = max(ans, sum(d for a, b, c, d in zip(A, B, C, D) if l[b] - l[a] == c))

print(ans)

Submission status: Accepted

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

for A in itertools.combinations_with_replacement(range(1, m + 1), n):
    flag = 0
    for k in range(n - 1):
        if A[k + 1] < A[k]:
            flag = 1
    if flag == 0:
        point = 0
        for l in range(q):
            if A[lst[l][1] - 1] - A[lst[l][0] - 1] == lst[l][2]:
                point += lst[l][3]
        ans = max(ans, point)

print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations_with_replacement
def input(): return sys.stdin.readline().strip()


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

    LIST = [i for i in range(1, M + 1)]
    ans = 0
    for A in list(combinations_with_replacement(LIST, N)):
        val = 0
        for a, b, c, d in pair:
            if A[b] - A[a] == c:
                val += d
        ans = max(ans, val)
        #print("val={}, A={}".format(val, A))
    print(ans)



    


if __name__ == "__main__":
    main()

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
    answer = 0
    for AA in combinations_with_replacement(range(1,M+1),r=N):
        
        tmp_ans = 0
        for q in range(Q):
            if AA[b[q]-1] - AA[a[q]-1] ==  c[q]:
                tmp_ans += d[q]
  
        answer = max(answer,tmp_ans)
    print(answer)
    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:
N,M,Q = list(map(int,input().split()))

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

l = []

def perm(l1,i,depth):
    if depth == N:
        l.append(l1)
    else:
        for j in range(i,M+1):
            l2 = list(l1)
            l2.append(j)
            perm(l2,j,depth+1)

perm([],1,0)

ans = 0

def smax(a,b):
    if a>b:
        return a
    else:
        return b

for ll in l:
    score = 0
    for i in range(Q):
        if ll[D[i][1]-1]-ll[D[i][0]-1]==D[i][2]:
            score += D[i][3]
    ans =  smax(score,ans)


print(ans)