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:
# -*- coding: utf-8 -*-


# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    n, m, q = input_to_int_map()
    kumis = [input_to_int_tuple() for i in range(q)]

    import itertools

    rets = [0]
    for comb in itertools.combinations_with_replacement(range(1, m + 1), n):
        val = 0
        for kumi in kumis:
            if (comb[kumi[1] - 1] - comb[kumi[0] - 1]) == kumi[2]:
                val += kumi[3]

        rets.append(val)

    print(max(rets))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools
N, M, Q = map(int, input().split())
nums = [list(map(int, input().split())) for _ in range(Q)]
# print(nums)
# 長さN
# 数字はMまで
num_permutations = list(
    map(list, itertools.combinations_with_replacement(list(range(1, M + 1)), N)))
# print(num_permutations)

maxcount = 0
for num_permutation in num_permutations:
    count = 0
    # print(num_permutation)
    for num in nums:
        # print(num)
        if num_permutation[num[1] - 1] - num_permutation[num[0] - 1] == num[2]:
            count += num[3]
            # print(num[3])
    maxcount = max(maxcount, count)
    # print(count)
    # print('=======================')
print(maxcount)

Submission status: Accepted

Solution code:
ans=0
N,M,QQ=map(int,input().split())
Q=[]
for _ in range(QQ):
    a,b,c,d=map(int,input().split())
    Q.append([a,b,c,d])
def check(a):
    tmp=0
    for q in Q:
        if a[q[1]]-a[q[0]]==q[2]:
            tmp+=q[3]
    return tmp

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):
                                        ans=max(ans,check([0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10]))
print(ans)

Submission status: Accepted

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

import itertools as itr

ans = 0
img = 0

for num in itr.combinations_with_replacement(range(1,M+1), N):
    img = 0
    for a, b, c, d in lst:
        if num[b-1]-num[a-1] == c:
            img += d

    if img >= ans:
        ans = img


print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

n, m, q = [int(x) for x in input().split()]
c_list = [[int(x) for x in input().split()] for _ in range(q)]

ans = 0
for temp in list(combinations_with_replacement(range(1, m + 1), n)):
    d_sum = 0
    for a, b, c, d in c_list:
        if temp[b - 1] - temp[a - 1] == c:
            d_sum += d
    if d_sum > ans:
        ans = d_sum
print(ans)

Submission status: Accepted

Solution code:
# ABC165d


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    # 再帰関数を使わない限りPypyで出すこと

    def dump(*args):
        sys.stderr.write(str(args))

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

    b = []

    def create():
        if len(b) >= n:
            t = eval()
            return t
        an = 0
        s = b[-1] if len(b) > 0 else 1
        for j in range(s, m + 1):
            b.append(j)
            an = max(an, create())
            b.pop()
        return an

    def eval():
        ans = 0

        for l in a:
            if b[l[1]-1] - b[l[0]-1] == l[2]:
                ans += l[3]
        #print(b, ans)
        return ans

    print(create())


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

my_list = list(range(1,M+1))
x = combinations_with_replacement(my_list, N)
high_score = 0
for i in x:
  score = 0
  for q in Q_list:
    if i[q[1]-1] - i[q[0]-1] == q[2]:
      score += q[3]
  high_score = max(high_score, score)
      
print(high_score)

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
requirements = {}
for _ in range(Q):
    A, B, C, D = map(int, input().split())
    requirements[(A, B, C)] = D

def get_score(A):
    global requirements
    score = 0
    for elt in requirements:
        if A[elt[1]-1] - A[elt[0]-1] == elt[2]:
            score += requirements[elt]
    return score

A = []
ans = 0

def solve(A):
    global ans
    global requirements
    if len(A) == 0:
        for integer in range(1, M+1):
            solve(A + [integer])
    elif len(A) < N:
        for integer in range(A[-1], M+1):
            solve(A + [integer])
            
    else:
        ans = max(ans, get_score(A))
        

solve(A)
print(ans)

Submission status: Accepted

Solution code:
import itertools

N, M, Q = map(int, input().split())
A = [int(i + 1) for i in range(M)]
abcd = [[int(j) for j in input().split()] for i in range(Q)]
ans = 0
for i in itertools.combinations_with_replacement(A, N):
	a = 0
	for j in abcd:
		if i[j[1] - 1] - i[j[0] - 1] == j[2]:
			a += j[3]
	ans = max(a, ans)
print(ans)

Submission status: Accepted

Solution code:
import itertools
#import time

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

#print(arr)

numbers = [i for i in range(1, m+1)]
a = list(itertools.combinations_with_replacement(numbers, n))

sum_ = 0
for i in a:
    #print(i)
    #time.sleep(1999)
    tmp = 0
    for j in arr:
        if i[j[1]-1]-i[j[0]-1] == j[2]:
            tmp += j[3]
    if tmp > sum_:
        sum_ = tmp

print(sum_)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def calc(nums):
        ret = 0
        for a, b, c, d in mat:
            if nums[b - 1] - nums[a - 1] == c:
                ret += d

        return ret

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

    ans = 0

    from collections import deque

    que = deque()
    que.append(([1], 1, 1))
    # 本体、長さ、右はじ

    while que:
        nums, l, right = que.pop()

        if l == n:
            temp = calc(nums)
            ans = max(ans, temp)
        else:
            for i in range(right, m + 1):
                nex = nums + [i]
                que.append((nex, l + 1, i))

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

MOD = 10**9+7

n,m,q = get_nums_l()
abcd = []
for _ in range(q):
    s = input()
    abcd.append(list(map(int, s.split())))
#abcd = list(map(lambda s: list(map(int, s.split())), map(lambda s: s.strip(), sys.stdin.readlines())))

def solve(A):
    score = 0
    for query in abcd:
        if A[query[1]-1] - A[query[0]-1] == query[2]:
            score += query[3]
    return score


ans = 0

def dfs(A):
    global ans
    if len(A) == n:
        # log(A)
        ans = max(ans, solve(A))
    elif len(A) == 0:
        for a in range(1, m+1):
            dfs([a])
    else:
        for a in range(A[-1], m+1):
            dfs(A+[a])

dfs([])
print(ans)

Submission status: Accepted

Solution code:
n,m,q = map(int,input().split())
l = []
res = 0
for _ in range(q):
    l.append(tuple(map(int,input().split())))
    
def pt(a):
    r = 0
    for il in l:
        if a[il[1]-1] - a[il[0]-1] == il[2]:
            r += il[3]
    return r

def g(a):
    if len(a) == 0:
        for i in range(1,m+1):
            g(a+[i])
    elif len(a) < n:
        for i in range(a[-1],m+1):
            g(a+[i])
    else:
        global res
        res = max(res, pt(a))

g([])

print(res)

Submission status: Accepted

Solution code:
import itertools

if True:
    n, m, q = map(int, input().split())
    aa = [0] * q
    bb = [0] * q
    cc = [0] * q
    dd = [0] * q
    for i in range(q):
        a, b, c, d = map(int, input().split())
        aa[i] = a - 1
        bb[i] = b - 1
        cc[i] = c
        dd[i] = d

ans = 0
ma = None
for a in itertools.combinations_with_replacement(list(range(1, m + 1)), n):
    x = 0
    for i in range(q):
        if a[bb[i]] - a[aa[i]] == cc[i]:
            x += dd[i]
    if x > ans:
        ma = a
    ans = max(ans, x)
print(ans)

Submission status: Accepted

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

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

import itertools
seq = list(range(1,m+1))
lis_p = list(itertools.combinations_with_replacement(seq, n))

ans = 0
ans_max = 0

for li_p in lis_p:
    for li in lis:
        if li_p[li[1]-1] - li_p[li[0]-1] == li[2]:
            ans += li[3]
    #print(li_p, ans)
    if ans > ans_max:
        ans_max = ans
    ans = 0

print(ans_max)

Submission status: Accepted

Solution code:
import itertools
def nasu(s, l):
  n = N - 2
  T = []
  for i in range(s, l + 1):
    T.append(i)
  L = list(itertools.combinations_with_replacement(T, n))
  ans = 0
  for i in L:
    P = [s] + list(i) + [l]
    ans = max(ans, honya(P))
  return ans

def honya(L):
  ans = 0
  for a, b, c, d in abcd:
    a -= 1
    b -= 1
    if L[b] - L[a] == c:
      ans += d
  return ans

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

ans = 0
for i in range(1, M + 1):
  for j in range(i, M + 1):
    ans = max(ans, nasu(i, j))

print(ans)

Submission status: Accepted

Solution code:
import itertools


def main():
    # S = input()
    N, M, Q = list(map(int, input().split(' ')))
    
    inputs = []
    for _ in range(Q):
        inputs.append(list(map(int, input().split(' '))))
    
    out = 0    
    # inputs = sorted(inputs, key=lambda x: x[-1], reverse=True)
    # print(inputs)

    # A = [0]*N
    # for i in range(M):
    #     for j in range(i, M):
    # As = list(itertools.combinations([i for i in range(1, M+1)], N))
    As = list(itertools.combinations_with_replacement([i for i in range(1, M+1)], N))
    
    # print(As)

    tmp = 0

    # print('--')
        
    
    for A in As:
        out = 0
        for i in range(len(inputs)):
            
            ai = inputs[i][0]
            bi = inputs[i][1]
            ci = inputs[i][2]
            di = inputs[i][3]
        
            if A[bi-1] - A[ai-1] == ci:
                # print(A, di)
                out += di
            tmp = max(tmp, out)
        # print('---')
    print(tmp)
                
        
        
        
    
    

    
    
main()

Submission status: Accepted

Solution code:

MOD = 10 ** 9 + 7

def main():
    for _ in inputt(1):
        N, M, Q = inputi()
        B = inputl(Q)
        def S(l):
            return sum(d for a, b, c, d in B if l[b - 1] - l[a - 1] == c)
        @lru_cache(None)
        def L(n, i):
            if not n:
                return [[]]
            R = []
            for ni in range(i, M):
                for l in L(n - 1, ni):
                    R.append([ni] + l)
            return R
        print(max(S(l) for l in L(N, 0)))




# region M


# region import

from math import *
from heapq import *
from itertools import *
from functools import reduce, lru_cache, partial
from collections import Counter, defaultdict
import re, copy, operator, cmath
import sys, io, os, builtins
sys.setrecursionlimit(1000)

# endregion

# region fastio

BUFSIZE = 8192
class FastIO(io.IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = io.BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(io.IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
def print(*args, **kwargs):
    if args:
        sys.stdout.write(str(args[0]))
        split = kwargs.pop("split", " ")
        for arg in args[1:]:
            sys.stdout.write(split)
            sys.stdout.write(str(arg))
    sys.stdout.write(kwargs.pop("end", "\n"))
def debug(*args, **kwargs):
    print("debug", *args, **kwargs)
    sys.stdout.flush()
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip()
inputt = lambda t = 0: range(t) if t else range(int(input()))
inputs = lambda: input().split()
inputi = lambda k = int: map(k, inputs())
inputl = lambda t = 0, k = lambda: list(inputi()): [k() for _ in range(t)] if t else list(k())

# endregion

# region bisect

def len(a):
    if isinstance(a, range):
        return -((a.start - a.stop) // a.step)
    return builtins.len(a)
def bisect_left(a, x, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    if key == None: key = do_nothing
    while lo < hi:
        mid = (lo + hi) // 2
        if key(a[mid]) < x: lo = mid + 1
        else: hi = mid
    return lo
def bisect_right(a, x, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    if key == None: key = do_nothing
    while lo < hi:
        mid = (lo + hi) // 2
        if x < key(a[mid]): hi = mid
        else: lo = mid + 1
    return lo
def insort_left(a, x, key = None, lo = 0, hi = None):
    lo = bisect_left(a, x, key, lo, hi)
    a.insert(lo, x)
def insort_right(a, x, key = None, lo = 0, hi = None):
    lo = bisect_right(a, x, key, lo, hi)
    a.insert(lo, x)
do_nothing = lambda x: x
bisect = bisect_right
insort = insort_right
def index(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    if key == None: key = do_nothing
    i = bisect_left(a, x, key, lo, hi)
    if lo <= i < hi and key(a[i]) == x: return a[i]
    if default != None: return default
    raise ValueError
def find_lt(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    i = bisect_left(a, x, key, lo, hi)
    if lo < i <= hi: return a[i - 1]
    if default != None: return default
    raise ValueError
def find_le(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    i = bisect_right(a, x, key, lo, hi)
    if lo < i <= hi: return a[i - 1]
    if default != None: return default
    raise ValueError
def find_gt(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    i = bisect_right(a, x, key, lo, hi)
    if lo <= i < hi: return a[i]
    if default != None: return default
    raise ValueError
def find_ge(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    i = bisect_left(a, x, key, lo, hi)
    if lo <= i < hi: return a[i]
    if default != None: return default
    raise ValueError

# endregion

# region csgraph
# TODO

class Tree:
    def __init__(n):
        self._n = n
        self._conn = [[] for _ in range(n)]
        self._list = [0] * n
    def connect(a, b):
        pass

# endregion

# region ntheory

class Sieve:
    def __init__(self):
        self._n = 6
        self._list = [2, 3, 5, 7, 11, 13]
    def extend(self, n):
        if n <= self._list[-1]: return
        maxbase = int(n ** 0.5) + 1
        self.extend(maxbase)
        begin = self._list[-1] + 1
        newsieve = [i for i in range(begin, n + 1)]
        for p in self.primerange(2, maxbase):
            for i in range(-begin % p, len(newsieve), p):
                newsieve[i] = 0
        self._list.extend([x for x in newsieve if x])
    def extend_to_no(self, i):
        while len(self._list) < i: 
            self.extend(int(self._list[-1] * 1.5))
    def primerange(self, a, b):
        a = max(2, a)
        if a >= b: return
        self.extend(b)
        i = self.search(a)[1]
        maxi = len(self._list) + 1
        while i < maxi:
            p = self._list[i - 1]
            if p < b:
                yield p
                i += 1
            else: return
    def search(self, n):
        if n < 2: raise ValueError
        if n > self._list[-1]: self.extend(n)
        b = bisect(self._list, n)
        if self._list[b - 1] == n: return b, b
        else: return b, b + 1
    def __contains__(self, n):
        if n < 2: raise ValueError
        if not n % 2: return n == 2
        a, b = self.search(n)
        return a == b
    def __getitem__(self, n):
        if isinstance(n, slice):
            self.extend_to_no(n.stop + 1)
            return self._list[n.start: n.stop: n.step]
        else:
            self.extend_to_no(n + 1)
            return self._list[n]

sieve = Sieve()
def isprime(n):
    if n <= sieve._list[-1]:
        return n in sieve
    for i in sieve:
        if not n % i: return False
        if n < i * i: return True
prime = sieve.__getitem__
primerange = lambda a, b = 0: sieve.primerange(a, b) if b else sieve.primerange(2, a)
def factorint(n):
    factors = []
    for i in sieve:
        if n < i * i: break
        while not n % i:
            factors.append(i)
            n //= i
    if n != 1: factors.append(n)
    return factors
factordict = lambda n: Counter(factorint(n))

# endregion

# region main

if __name__ == "__main__":
    main()

# endregion


# endregion

Submission status: Accepted

Solution code:
import itertools

N, M, Q = map(int, input().split())
M_list = list(range(1, M+1))
Q_list = []
points = []

for _ in range(Q):
    Q_list.append(list(map(int, input().split())))

for i in itertools.combinations_with_replacement(M_list, N):
    point = 0
    for a, b, c, d in Q_list:
        if i[b-1] - i[a-1] == c:
            point += d
        points.append(point)

print(max(points))

Submission status: Accepted

Solution code:
import sys
import math
import itertools 
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,M,Q=nm()
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]=nm()

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

sumd=0
sumd_max=0
for alist in A_cmb:
    for i in range(Q):
        if(alist[b[i]-1]-alist[a[i]-1]==c[i]):
            sumd+=d[i]
    if(sumd>sumd_max):
        sumd_max=sumd
    sumd=0

print(sumd_max)

Submission status: Accepted

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

num = [i for i in range(1, M+1)]
# print(num)
ans = 0

for v in itertools.combinations_with_replacement(num, N):
    # print(v)
    vsum = 0
    for i in range(Q):
        # print(info[i][0], info[i][1], info[i][2], info[i][3])
        if v[info[i][1]-1] - v[info[i][0]-1] == info[i][2]:
            vsum += info[i][3]
    # print(vsum)
    ans = max(ans, vsum)

print(ans)

Submission status: Accepted

Solution code:
import itertools

n, m, q = map(int, input().split())
a = []
b = []
c = []
d = []
for _ in range(q):
    a_, b_, c_, d_ = map(int, input().split())
    a.append(a_)
    b.append(b_)
    c.append(c_)
    d.append(d_)

max_score = -1
for v in itertools.combinations_with_replacement(tuple(range(1, m+1)), n):
    scores = []
    for i in range(q):
        if v[b[i]-1] - v[a[i]-1] == c[i]:
            scores.append(d[i])
    score = sum(scores)
    if max_score < score:
        max_score = score
print(max_score)

Submission status: Accepted

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

def next(an):
  for i in range(n)[::-1]:
    if an[i]==m:
      an[i]=0
    else:
      an[i] += 1
      break
  for i in range(n-1):
    if an[i+1]==0:
      an[i+1] = an[i]
  return an

an = [1] * n
max_score = 0

while True:
  score = 0
  if an[0]==0:
    break
  for i in range(q):
    a,b,c,d = cons[i]
    if an[b-1] - an[a-1] == c:
      score += d
  if score > max_score:
    max_score = score
  an = next(an)

print(max_score)

Submission status: Accepted

Solution code:
# Code for C - Many Requirements
# Use input() to fetch data from STDIN
[n, m, q] = map(int, input().split())
a = [0 for x in range(q)]
b = [0 for x in range(q)]
c = [0 for x in range(q)]
d = [0 for x in range(q)]

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

max_score = 0
def g(A, depth):
    global max_score
    if depth == 0:
        score = 0
        for i in range(q):
            if A[b[i] - 1] - A[a[i] - 1] == c[i]:
                score += d[i]
        if score > max_score:
            max_score = score
        return

    if len(A) == 0:
        for i in range(1, m + 1):
            g([i], depth - 1)
            return

    for i in range(A[-1], m + 1):
        g(A + [i], depth - 1)

g([], n)

print(max_score)

Submission status: Accepted

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**5+10)
input = sys.stdin.readline

import itertools
N,M,Q = MI()
l = LI2(Q)
result=0
nums = list(range(1,M+1))
for balls in itertools.combinations_with_replacement(nums, N):
    ans = 0
    for i in range(Q):
        if balls[l[i][1]-1]-balls[l[i][0]-1]==l[i][2]:
            ans += l[i][3]
    result = max(ans,result)
print(result)

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)]
num_ls = [i for i in range(1, m+1)]

comb = combinations_with_replacement(num_ls, n)
ans = 0
for v in comb:
    cnt = 0
    for a, b, c, d in abcd:
        if v[b-1] - v[a-1] == c:
            cnt += d
    ans = max(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

abcd = [[int(0) for I in range(4)] for II in range(Q)]
for i in range(Q):
    abcd[i] = list(map(int, input().split()))

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

ans=0
for x in pat:
    tmp=0
    for xx in abcd:
        if x[xx[1]-1] - x[xx[0]-1] == xx[2]:
            tmp+=xx[3]
    
    if ans<=tmp:
        ans=tmp

print(ans)

Submission status: Accepted

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

li = [x for x in range(1, M+1)]
Com = itertools.combinations_with_replacement(li, N)

ans=0
for com in Com:
    reg=0
    for a,b,c,d in P:
        if com[b-1] - com[a-1] == c:
            reg += d
    ans = max(reg, ans)
print(ans)

Submission status: Accepted

Solution code:
N,M,Q=map(int,input().split())
s=[list(map(int, input().split())) for i in range(Q)]
def ju(N,a,l):
    k=[]
    if N==1:
        for i in range(a,M+1):
            k+=[l+[i]]
    else:
        for i in range(a,M+1):
            k+=ju(N-1,i,l+[i])
    return k
l=ju(N,1,[])
a=0
for i in l:
    t=0
    for j in s:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            t+=j[3]
    if t>a:
        a=t
print(a)

Submission status: Accepted

Solution code:
import itertools
import copy

n,m,q = map(int,input().split())
a = [[0]*4]*q
for i in range(q):
	a[i] = list(map(int,input().split()))

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

chanpion=0
for cand in candidate:
  point=0
  for l in range(q):
    if cand[a[l][1]-1]-cand[a[l][0]-1]==a[l][2]:
    	point += a[l][3]
  if point>chanpion:
    chanpion=copy.copy(point)
    
print(chanpion)

Submission status: Accepted

Solution code:
def jisuan():
    global s
    s1=0
    for i in range(q):
        if A[b[i]-1]-A[a[i]-1]==c[i]:
            s1+=d[i]
    s=max(s,s1)


def dg1(w):
    if w==n:
        jisuan()
        return
    for i in range(A[w-1],m+1):
        A[w]=i
        dg1(w+1)


def dg():
    for i in range(1,m+1):
        A[0]=i
        dg1(1)


n,m,q=map(int,input().split())
s=0
# ai<=m
# A一共n个
a,b,c,d=[],[],[],[]
for i in range(q):
    x=list(map(int,input().split()))
    a.append(x[0])
    b.append(x[1])
    c.append(x[2])
    d.append(x[3])
A=[0]*n
dg()
print(s)

Submission status: Accepted

Solution code:
import itertools
def LI(): return list(map(int,input().split()))
N,M,Q = LI()
abcd = [LI() for _ in range(Q)]
ans = 0
for x in itertools.combinations_with_replacement(range(1,M+1),N):
    score = 0
    for y in abcd:
        a,b,c,d = y[0],y[1],y[2],y[3]
        if x[b-1]-x[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())
Q = [list(map(int, input().split())) for i in range(q)]
m = [i for i in range(1, m+1)]
p = itertools.combinations_with_replacement(m, n)

ans = []
for v in p:
    count = 0
    for i in Q:
        if v[i[1]-1]-v[i[0]-1] == i[2]:
            count += i[3]
    ans.append(count)
print(max(ans))

Submission status: Accepted

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


from itertools import combinations_with_replacement

cands = list(combinations_with_replacement(range(1,m+1), n))

ans = 0

for cand in cands:
  score = 0
  for a,b,c,d in nums:
    if cand[b] - cand[a] == c:
      score += d
  ans = max(ans, score)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys
sys.setrecursionlimit(10**9)
# input=sys.stdin.readline
from collections import deque
import heapq
from itertools import combinations

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

l=[]
for i in range(q):
    l.append(list(map(int,input().split())))
x=[i for i in range(n+m-1)]
com=list(combinations(x,m-1))
ans=0
for i in com:
    z=[]
    f=0
    p=1
    # print(i)
    for j in range(m+n-1):
        if j in i:
            p+=1
            continue
        z.append(p)
    tmp=0
    for j in range(q):
        a,b,c,d=l[j]
        a-=1
        b-=1
        if z[b]-z[a]==c:
            tmp+=d
    ans=max(ans,tmp)
print(ans)