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

def ascending(ndig, first_digit_max):
    for x in range(1, first_digit_max+1):
        if ndig == 1:
            yield [x]
        else:
            for y in ascending(ndig-1, x):
                yield y+[x]

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

    d_sum_max = 0

    for A in As:
        d_sum = 0
        for i in range(Q):
            if A[b[i]-1]-A[a[i]-1]==c[i]:
                d_sum += d[i]
        d_sum_max = max(d_sum, d_sum_max)

    print(d_sum_max)
    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:
from itertools import combinations_with_replacement

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

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

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

ans = 0
for p in list(combinations_with_replacement(l, N)):
  temp = 0
  for c in C:
    #print(c, p)
    if p[c[1] - 1] - p[c[0] - 1] == c[2]:
      temp += c[3]
      
  ans = max(ans, temp)
  
print(ans)

Submission status: Accepted

Solution code:
n, m, q = list(map(int, input().split(' ')))

aq = [None] * q
bq = [None] * q
cq = [None] * q
dq = [None] * q
for i in range(q):
    aq[i], bq[i], cq[i], dq[i] = list(map(int, input().split(' ')))

result = 0

def dfs(i, ary):
    global result
    if i == n:
        val = 0
        for j in range(q):
            if ary[bq[j] - 1] - ary[aq[j] - 1] == cq[j]:
                val += dq[j]
        if result < val:
            result = val
    else:
        if ary == []:
            for c in range(1, m + 1):
                dfs(i + 1, [c])
        else:
            l = ary[-1]
            for c in range(l, m + 1):
                dfs(i + 1, ary + [c])

dfs(0, [])

print(result)

Submission status: Accepted

Solution code:
n , m , q = map(int,input().split())
p = []
for i in range(q):
    a , b , c , d = map(int,input().split())
    p.append([a,b,c,d])
ans = 0
for a1 in range(1,m+1):
    for a2 in range(a1,m+1):
        for a3 in range(a2,m+1):
            for a4 in range(a3,m+1):
                for a5 in range(a4,m+1):
                    for a6 in range(a5,m+1):
                        for a7 in range(a6,m+1):
                            for a8 in range(a7,m+1):
                                for a9 in range(a8,m+1):
                                    for a10 in range(a9,m+1):
                                        tyu = [0,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10]
                                        kar = 0
                                        for x,y,z,w in p:
                                            if tyu[y] - tyu[x] == z:
                                                kar += w
                                        ans = max(kar,ans)
print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m,q = map(int,input().split())
input_lines = [[int(j) for j in input().split()]for i in range(q)]

#数列の列挙
li = list(itertools.combinations_with_replacement(range(1,m+1),n))

ans=0
for l in li:
    result = 0
    for line in input_lines:
        if (l[line[1]-1]-l[line[0]-1])==(line[2]):
            result+=line[3]
    if result>ans:
        ans=result
print(ans)

Submission status: Accepted

Solution code:
N, M, Q = [int(i) for i in input().split()]
abcd = [[int(i) for i in input().split()] for _ in range(Q)]
ans = 0
ary = [1]*N
while True:
    cnt = 0
    for l in abcd:
        a, b, c, d = l
        if ary[b - 1] - ary[a - 1] == c:
            cnt += d
    ans = max(ans, cnt)
    ary[-1] += 1
    i = len(ary)-1
    try:
        while ary[i] > M:
            ary[i - 1] += 1
            i -= 1
    except IndexError:
        break
    i += 1
    while i < len(ary):
        ary[i] = ary[i - 1]
        i+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import itertools

n,m,q = na()
l = []

for p in itertools.combinations_with_replacement(range(1,m+1), n):
    l.append(p)

ans = 0
abcd = []

for i in range(q):
    a,b,c,d = na()
    abcd.append((a,b,c,d))

for ll in l:
    dd = 0
    k = sorted(ll)
    for a,b,c,d in abcd:
        dd += d if k[b-1]-k[a-1] == c else 0
    ans = max(ans,dd)

print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, deque
from sys import exit
import math

def calc(arr, query):
    ret = 0
    # print(arr)\
    for q in query:
        if arr[q[1] - 1] - arr[q[0] - 1] == q[2]:
            ret += q[3]

    return ret

def dfs(n, m, query, tlen, tail, score, deq):
    if tlen == n:
        return calc(list(deq), query)
    else:
        for i in range(tail, m+1):
            deq.append(i)
            ret = dfs(n, m, query, tlen+1, i, score, deq)
            if ret > score:
                score = ret
            deq.pop()

    return score




def main():
    n,m,q = getList()
    query = []
    for _ in range(q):
        query.append(getList())
    deq = deque([1])
    ans = dfs(n, m ,query, 1, 1, 0, deq)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def dfs(prev,length,n,m,lists,A):

    if length == n+1:
        res = 0
        for lis in lists:
            if A[lis[1]-1] - A[lis[0]-1] == lis[2]:
                res += lis[3]
        return res
    else:
        res = 0  
        for i in range(prev,m+1):
            Atmp = A + [i]
            res = max(res,dfs(i,length+1,n,m,lists,Atmp))
        return res

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

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

print(dfs(1,1,N,M,lists,[]))

Submission status: Accepted

Solution code:
import itertools

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

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

L = [x+1 for x in range(M)]
L2 = []

p_tuple = itertools.combinations_with_replacement(L, N)

for i, p in enumerate(p_tuple):
    tmp = p[0]
    for pp in p:
        if pp < tmp:
            break
        else:
            tmp = pp
    else:
        L2.append(list(p))

ans = 0
for l2 in L2:
    tmpmax = 0
    for qq in query:
        if l2[qq[1]-1] - l2[qq[0]-1] == qq[2]:
            tmpmax += qq[3]
    ans = max(ans, tmpmax)

print(ans)

Submission status: Accepted

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

from itertools import combinations_with_replacement

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

ans = 0
for i in list(combinations_with_replacement(A,N)):
    p = 0
    for j in range(Q):
        if i[data[j][1]-1]-i[data[j][0]-1] == data[j][2]:
            p += data[j][3]
    ans = max(ans,p)

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)]
l=list(range(1,m+1))
l=list(itertools.combinations_with_replacement(l,n))
ans=0
for i in l:
  kari=0
  for j in range(q):
    if i[abcd[j][1]-1]-i[abcd[j][0]-1]==abcd[j][2]:
      kari+=abcd[j][3]
  ans=max(ans,kari)
print(ans)

Submission status: Accepted

Solution code:
n, m, q = map(int, input().split())
li = [list(map(int, input().split())) for _ in range(q)]
s = [[1]]
res = []
while s:
    l = s.pop()
    if len(l) == n + 1:
        res.append(l)
    else:
        for i in range(l[-1], m + 1):
            s.append(l + [i])
ans = 0
for row in res:
    t = 0
    for a, b, c, d in li:
        if row[b] - row[a] == c:
            t += d
    ans = max(ans, t)
print(ans)

Submission status: Accepted

Solution code:
import copy
import sys

sys.setrecursionlimit(100000)
N, M, Q = map(int, input().split())
kumi = list()
max_score = 0

def dfs(a):
    global N
    global Q
    global max_score
    global kumi
    if len(a) == N:
        # print(a)
        score = 0
        for k in kumi:
           if a[k[1]-1] - a[k[0]-1] == k[2]:
               score += k[3]
        max_score = max(max_score, score)
        return

    for i in range(a[-1], M+1):
        next = copy.copy(a)
        next.append(i)
        dfs(next)

for i in range(Q):
    kumi.append(list(map(int, input().split())))

dfs([1])
print(max_score)

Submission status: Accepted

Solution code:
ans =  0

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

    def calc(array):
        global ans
        score = 0
        for a,b,c,d in q:
            if array[b]-array[a] == c:
                score += d
        ans = max(ans, score)

    def search(array):
        global count
        if len(array) == N+1:
            calc(array)
        else:
            for i in range(array[-1], M+1):
                search(array+[i,])
    search([1, ])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def calc(x, ls):
    s = sum([d for a, b, c, d in ls if x[b - 1] - x[a - 1] == c])
    return s

ans = 0
cands = range(1, m+1)
c = itertools.combinations_with_replacement(cands, n)
for x in c:
    ans = max(ans, calc(x, ls))
print(ans)

Submission status: Accepted

Solution code:
def saiki(bef,ind,b):
    global n
    if ind==n:
        #print(b)
        calc(b)
        return
    for i in range(1,m+1):
        if i<bef:
            continue
        saiki(i,ind+1,b+[i])
def calc(b):
    global q,info,ans
    aa=0
    for i in range(q):
        if b[info[i][1]-1]-b[info[i][0]-1]==info[i][2]:
            aa+=info[i][3]
    if ans<aa:
        ans=aa
n,m,q=map(int,input().split())
info=[]
for i in range(q):
    a,b,c,d=map(int,input().split())
    info.append([a,b,c,d])
ans=0
saiki(0,0,[])
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import numpy as np
# from itertools import *
# from collections import *

# S = input().split()
# N = int(input().split())
# K, N = [int(x) for x in input().split()]

from itertools import *

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

A = []
for n in list(combinations_with_replacement(range(1, N+1), M)):
    if n[0] == 1:
        A.append(n)
score = [0] * len(A)

for q in range(Q):
    a, b, c, d = [int(x) for x in input().split()]
    for idx, l in enumerate(A):
        if l[b-1] - l[a-1] == c:
            score[idx] += d

print(max(score))

Submission status: Accepted

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

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))


def getScore(ai, abcds):
    ret = 0
    for abcd in abcds:
        a,b,c,d = abcd
        if ai[b-1]-ai[a-1] == c:
            ret += d
    return ret


def main():
    n,m,q = na()
    abcds = [na() for _ in range(q)]
    nums = [i for i in range(1,m+1)]
    ans = 0
    for ai in itertools.combinations_with_replacement(nums, n):
        ans = max(ans, getScore(ai, abcds))
    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

As = [1] * N

def next(ls):
    if ls[-1] < M:
        ls[-1] += 1
    else:
        for i, elem in reversed(list(enumerate(ls))):
            if elem < M:
                for j in range(i, N):
                    ls[j] = elem + 1
                break
        else:
            return False
    return True

cond = True
max_score = 0
while cond:
    score = 0
    for a, b, c, d in ts:
        if As[b-1] - As[a-1] == c:
            score += d
    max_score = max(max_score, score)
    cond = next(As)

print(max_score)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as cwr

n, m, q = map(int, input().split())
lis = range(1, m + 1)
cdt = list(cwr(lis,n))
res = [0] * len(cdt)

for i in range(q):
    a, b, c, d = map(int, input().split())
    for j, k in enumerate(cdt):
        if k[b-1] - k[a-1] == c:
            res[j] += d
print(max(res))

Submission status: Accepted

Solution code:
n, m, q = map(int, input().split())
from collections import deque
a = deque([[i] for i in range(1, m+1)])
flag = True
while flag:
    s = a.popleft()
    for i in range(1, m + 1):
        if s[-1] <= i:
            if len(s) <= n-1:
                a.append(s+[i])
            else:
                flag = False
                break
a.append(s)
max_a = 0
ns = []
for i in range(q):
    ns.append(list(map(int, input().split())))
for ai in a:
    max_a = max(max_a, sum(ns[i][3] for i in range(q) if ai[ns[i][1] - 1] - ai[ns[i][0]-1] == ns[i][2]))
print(max_a)

Submission status: Accepted

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

def f():
    for A in combinations_with_replacement(range(1, M + 1), N):
        pa = 1
        for a in A:
            if a < pa:
                break
        else:
            yield list(A)

ans = 0
for A in f():
    point = 0
    for a, b, c, d in abcd:
        if A[b-1] - A[a-1] == c:
            point += d
    ans = max(ans, point)
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)]

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

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import itertools

# 標準入力の取得
N,M,Q = list(map(int, input().split()))
a,b,c,d = [],[],[],[]
for q in range(Q):
    a_q,b_q,c_q,d_q = list(map(int, input().split()))
    a.append(a_q)
    b.append(b_q)
    c.append(c_q)
    d.append(d_q)

# 求解処理
l = list(range(1, M+1))
result = 0
for A in itertools.combinations_with_replacement(l, N):
    score = 0
    for a_i,b_i,c_i,d_i in zip(a, b, c, d):
        if A[b_i-1] - A[a_i-1] == c_i:
            score += d_i

    result = max(result, score)

# 結果出力
print(result)

Submission status: Accepted

Solution code:
def solve(arr, abcd, Q):
    ans = 0
    for i in range(Q):
        if arr[abcd[i][1]-1]-arr[abcd[i][0]-1] == abcd[i][2]:
            ans += abcd[i][3]
    return ans


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

ans = 0
for i1 in range(1, M+1):
    for i2 in range(1, M+1):
        if i1 > i2:
            continue
        if N == 2:
            tmp = [i1, i2]
            tmp_ans = solve(tmp, abcd, Q)
            ans = max(tmp_ans, ans)

        for i3 in range(1, M+1):
            if i2 > i3:
                continue
            if N == 3:
                tmp = [i1, i2, i3]
                tmp_ans = solve(tmp, abcd, Q)
                ans = max(tmp_ans, ans)

            for i4 in range(1, M+1):
                if i3 > i4:
                    continue
                if N == 4:
                    tmp = [i1, i2, i3, i4]
                    tmp_ans = solve(tmp, abcd, Q)
                    ans = max(tmp_ans, ans)

                for i5 in range(1, M+1):
                    if i4 > i5:
                        continue
                    if N == 5:
                        tmp = [i1, i2, i3, i4, i5]
                        tmp_ans = solve(tmp, abcd, Q)
                        ans = max(tmp_ans, ans)

                    for i6 in range(1, M+1):
                        if i5 > i6:
                            continue
                        if N == 6:
                            tmp = [i1, i2, i3, i4, i5, i6]
                            tmp_ans = solve(tmp, abcd, Q)
                            ans = max(tmp_ans, ans)

                        for i7 in range(1, M+1):
                            if i6 > i7:
                                continue
                            if N == 7:
                                tmp = [i1, i2, i3, i4, i5, i6, i7]
                                tmp_ans = solve(tmp, abcd, Q)
                                ans = max(tmp_ans, ans)

                            for i8 in range(1, M+1):
                                if i7 > i8:
                                    continue
                                if N == 8:
                                    tmp = [i1, i2, i3, i4, i5, i6, i7, i8]
                                    tmp_ans = solve(tmp, abcd, Q)
                                    ans = max(tmp_ans, ans)

                                for i9 in range(1, M+1):
                                    if i8 > i9:
                                        continue
                                    if N == 9:
                                        tmp = [i1, i2, i3, i4,
                                               i5, i6, i7, i8, i9]
                                        tmp_ans = solve(tmp, abcd, Q)
                                        ans = max(tmp_ans, ans)

                                    for i10 in range(1, M+1):
                                        if i9 > i10:
                                            continue
                                        if N == 10:
                                            tmp = [i1, i2, i3, i4,
                                                   i5, i6, i7, i8, i9, i10]
                                            tmp_ans = solve(tmp, abcd, Q)
                                            ans = max(tmp_ans, ans)
print(ans)

Submission status: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, M, Q = iim()
    A = [list(iim()) for i in range(Q)]

    def f(aa, i):
        ans = 0
        if i < N:
            for j in range(aa[i], M+1):
                aa[i+1] = j
                ans = max(ans, f(aa, i+1))
            return ans

        for ai, bi, ci, di in A:
            if aa[bi] - aa[ai] == ci:
                ans += di
        return ans

    print(f([1]*(N+1), 0))

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from itertools import (
    accumulate,  # 累積和のイテレータ
    groupby,  # 値をkey,同じ値の集まりをgroup
    permutations,  # 順列
    combinations,  # 組み合わせ
    product,  # 重複あり順列（直積, 深いネストにも使える）
    combinations_with_replacement,  # 重複あり組み合わせ
)

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

ans = 0
for v in combinations_with_replacement(range(1, M+1), N):
    score = 0
    for i in range(Q):
        joken = q[i]
        if v[joken[1]-1] - v[joken[0]-1] == joken[2]:
            score += joken[3]
    ans = max(ans, score)
    #print(v, ': ', score)

print(ans)

Submission status: Accepted

Solution code:
import itertools
N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for i in range(Q)]
A_itr = itertools.combinations_with_replacement(range(1, M+1), N)
max_score = 0
for A in A_itr:
    score = 0
    for j_abcd in abcd:
        if A[j_abcd[1]-1]-A[j_abcd[0]-1] == j_abcd[2]:
            score += j_abcd[3]
    max_score = max(max_score, score)
print(max_score)

Submission status: Accepted

Solution code:
import itertools
n, m, q = map(int, input().split())
abcds = [list(map(int, input().split())) for _ in range(q)]
aaa = range(1, m + 1)
ans = 0
for a in itertools.combinations_with_replacement(aaa, n):
    list(a).sort()
    tmp = 0
    for abcd in abcds:
        if a[abcd[1] - 1] - a[abcd[0] - 1] == abcd[2]:
            tmp += abcd[3]
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 \
   /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/input.txt"
exit $?
'''
import sys
from itertools import combinations_with_replacement


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    n,m,q = _ia()
    a = []
    for _ in range(q):
        ai, bi, ci, di = _ia()
        a.append((ai-1, bi-1, ci, di))

    mx = 0
    for d in combinations_with_replacement([i for i in range(1,m+1)], n):
        tmp = 0
        for ai, bi, ci, di in a:
            if d[bi] - d[ai] == ci:
                tmp += di
        if tmp >= mx:
             mx = tmp
    return mx


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

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
X=[0]*Q
for i in range(Q):
    X[i] = list(map(int, input().split()))
from itertools import combinations_with_replacement
def solve(N,M,Q,X):
    ans = 0
    for c in combinations_with_replacement(range(1,M+1), N-1):
        A = [1]+list(c)
        score = 0
        for x in X:
            if A[x[1]-1]-A[x[0]-1]==x[2]:
                score += x[3]
        ans = max(ans,score)
    return ans
print(solve(N,M,Q,X))

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

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

for ii in range(n+1):
    As = [ca+[j]  for i,ca in enumerate(As) for j in range(ca[-1],m+1)]

ans=0
for A in As:
    temp=0
    for i in range(q):
        if A[b[i]-1]-A[a[i]-1] == c[i]:
            temp+=d[i]
    if temp>ans:
        ans=temp
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)
L=list(range(1,m+1))
cnt=[]
l=list(itertools.combinations_with_replacement(L,n))
for i in range(len(l)):
  Cnt=0
  tup=l[i]
  for j in range(q): 
    if int(tup[b[j]-1])-int(tup[a[j]-1])==int(c[j]):
      Cnt+=int(d[j])
  cnt.append(Cnt)
print(max(cnt))

Submission status: Accepted

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

def dfs(n,i,s,A):
    if n == N:
        A.append(s)
        return

    for j in range(i,M+1):
        tmp = s + [j]
        dfs(n+1,j,tmp,A)

def main():
    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())
        a[i] -= 1
        b[i] -= 1
    
    A = []
    ans = 0
    dfs(0,1,[],A)
    for B in A:
        tmp = 0
        for j in range(Q):
            if B[b[j]] - B[a[j]] == c[j]:
               tmp += d[j]

        ans = max(ans, tmp)

    print(ans) 



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
import collections
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 62


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


#
N, M, Q = lmi()
#
ABDC = llmi(Q)


def gen(arr=tuple()):
    score = 0
    if len(arr) == N:
        for a, b, c, d in ABDC:
            if arr[b - 1] - arr[a - 1] == c:
                score += d
        return score
    start = 0 if not arr else arr[-1]
    for i in range(start, M):
        score = max(score, gen(arr + (i,)))
    return score


print(gen())
#
# dp = [[-INF]*M for i in range(N+1)]
#
# for n in range(N):
#     for v in range(M):
#         # target: dp[n+1][v]

Submission status: Accepted

Solution code:
n, m, q = map(int, input().split())
a, b, c, d = [], [], [], []
for _ in range(q):
    i, j, k, l = map(int, input().split())
    a.append(i-1)
    b.append(j-1)
    c.append(k)
    d.append(l)

l = [[i] for i in range(1, m+1)]
for i in range(n-1):
    lcopy = []
    for j in l:
        for k in range(j[-1], m+1):
            lcopy.append(j + [k])
    l = lcopy

ans = []
for i in l:
    num = 0
    for j in range(q):
        if i[b[j]] - i[a[j]] == c[j]:
            num += d[j]
    ans.append(num)

print(max(ans))

Submission status: Accepted

Solution code:
import sys

if __name__ == '__main__':
    n, m, q = list(map(lambda x: int(x), sys.stdin.readline().split(' ')))
    lst = []
    for i in range(q):
        a,b,c,d = list(map(lambda x: int(x), sys.stdin.readline().split(' ')))
        lst += [[a-1,b-1,c,d]]
    lst = sorted(lst, key=lambda l:-l[3])

    score = 0
    seq = [1 for i in range(n)]
    seq[-1] = 0
    die = False
    # for i in range((n+1)*(m+1)):
    while True:
        tmpscore = 0
        seq[-1] += 1
        for j in reversed(range(len(seq))):
            if seq[j] == m + 1:
                if j-1 == -1:
                    die = True
                else:
                    seq[j-1] += 1
        if die:
            break
        for j in range(len(seq)):
            if seq[j] == m+1:
                seq[j] = seq[j-1]
        # print(seq)
        # seq完成
        for a, b, c, d in lst:
            if seq[b] - seq[a] == c:
                tmpscore += d
        if tmpscore > score:
            score = tmpscore
    print(score)

Submission status: Accepted

Solution code:
import itertools
n,m,q = map(int, input().split())
a = list()
b = list()
c = list()
d = list()
for i in range(q):
    hoge,hoge2,hoge3,hoge4 = map(int, input().split())
    a.append(hoge)
    b.append(hoge2)
    c.append(hoge3)
    d.append(hoge4)
l = list(range(1,m+1))
x = list(itertools.combinations_with_replacement(l,n))
max_point = 0
bestlist=0
for i in x:
    point = 0
    for j in range(q):
        if i[b[j]-1] - i[a[j]-1] == c[j]:
            point += d[j]
    max_point = max(point, max_point)
print(max_point)

Submission status: Accepted

Solution code:
# C - Many Requirements

n, m, q = map(int, input().split())
lst = []
for i in range(q):
    a, b, c, d = map(int, input().split())
    lst.append((a, b, c, d))  # 得点を先頭に

def allseq(n, m):
    if n == 0:
        yield []
    else:
        for rest in allseq(n - 1, m):
            for i in range(rest[-1] if len(rest) > 0 else 1, m+1):
                yield rest + [i]

x = 0
for seq in allseq(n, m):
    s = 0
    for a, b, c, d in lst:
        if seq[b-1] - seq[a-1] == c:
            s += d
    x = max(x, s)

print(x)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N,M,Q=mis()
    R = [lmis() for _ in range(Q)]
    ans = 0
    def rec(s):
        if len(s)==N:
            nonlocal ans
            ans = max(ans, sum(d for a,b,c,d in R if s[b-1]-s[a-1]==c))
        else:
            for i in range(s[-1], M+1):
                s.append(i)
                rec(s)
                s.pop()
    for i in range(1, M+1):
        rec([i])
    print(ans)



main()

Submission status: Accepted

Solution code:
import itertools
nt,mt,qt = input().split()
n, m, q = int(nt), int(mt), int(qt)
a = [0]*q
b = [0]*q
c = [0]*q
d = [0]*q
nums = [0]*m
for i in range(q):
	a[i], b[i], c[i], d[i] = map(int, input().split())
for i in range(m):
	nums[i] = i
ans = 0
for i in itertools.combinations_with_replacement(nums, n):
	anstmp = 0
	for j in range(q):
		if i[b[j]-1] - i[a[j]-1] == c[j]:
			anstmp += d[j]
	if anstmp > ans:
		ans = anstmp
print(ans)