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 math
import itertools
n, m, q = map(int, input().split())

abcd = []
for i in range(q):
    abcd.append(list(map(int, input().split())))

l = []
for i in range(1, m+1):
    l.append(i)

a_list = list(itertools.combinations_with_replacement(l, n))


max = 0
for i in range(len(a_list)):
    sum = 0
    for j in range(len(abcd)):
        if(a_list[i][abcd[j][1]-1] - a_list[i][abcd[j][0]-1]) == abcd[j][2]:
            sum += abcd[j][3]
    if sum >= max:
        max = sum


print(max)

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
a=[]
b=[]
c=[]
d=[]
for _ in range(q):
    a1,b1,c1,d1=map(int,input().split())
    a.append(a1)
    b.append(b1)
    c.append(c1)
    d.append(d1)

A=[1]*(n+1)
mx=0
while A[0]==1:
    s=0
    for i in range(0,q):
        if A[b[i]]-A[a[i]]==c[i]:s+=d[i]
    mx=max(mx,s)
    k=n
    while A[k]==m and k>=1:
        k-=1
    A[k]+=1
    for i in range(k+1,n+1):
        A[i]=A[i-1]
print(mx)

Submission status: Accepted

Solution code:
import itertools
l = list(map(int, input().split()))
li = []
for i in range(l[2]):
    li += [list(map(int, input().split()))]

araw = [i for i in range(1,l[1] + 1)]
a = []
for v in itertools.combinations_with_replacement(araw, l[0]):
    a += [list(v)]

r = []
for i in a:
    r_s = 0
    for j in li:
        if  i[j[1]-1] - i[j[0]-1] == j[2]:
            r_s += j[3]
    r += [r_s]
    
print(int(max(r)))

Submission status: Accepted

Solution code:
N, M , Q = list(map(int,input().split()))
L = []
for _  in range(Q):
    l = list(map(int,input().split()))
    L.append(l)
A = []
ans = []
def solve(A,i,ans):
    A.append(i)
    if len(A) >= N:
        #print(A)
        tmp = 0
        for x in L:
         #   print(x[1]-1,x[0]-1,A)
            if A[x[1] - 1] - A[x[0] - 1] == x[2]:
                tmp += x[3]
        ans.append(tmp)
        A.pop()
        return 
    pre = A[-1]
    for i in range(pre,M+1):
        solve(A,i,ans)
    A.pop()
solve(A,1,ans)
print(max(ans))

Submission status: Accepted

Solution code:
import itertools
from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

def combinations_with_replacement_count(n, r):
    return combinations_count(n + r - 1, r)

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

a_ = []
b_ = []
c_ = []
d_ = []
for i in range(q):
    a_.append(a[i][0])
    b_.append(a[i][1])
    c_.append(a[i][2])
    d_.append(a[i][3])

cnt = combinations_with_replacement_count(m, n)

m_ = []
for i in range(m):
    m_.append(i+1)

res_ = []
res = 0
h_list = list(itertools.combinations_with_replacement(m_,n))
for i in range(cnt):
    A = h_list[i]
    res = 0
    for l in range(q):
        if(A[b_[l]-1] - A[a_[l]-1] == c_[l]):
            res += d_[l]
    res_.append(res)

print(max(res_))

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

best = 0
seqlist = combinations_with_replacement(range(1,m+1),n)
for seq in seqlist:
	score = 0
	for x in qlist:
		if seq[x[1]-1] - seq[x[0]-1] == x[2]:
			score += x[3]
	if score > best:
		best = score
	
print(best)

Submission status: Accepted

Solution code:
from collections import Counter
import sys
sys.setrecursionlimit(200000)


def read():
    N, M, Q = map(int, input().split())
    ABCD = []
    for i in range(Q):
        a, b, c, d = map(int, input().split())
        ABCD.append((a, b, c, d))
    return N, M, Q, ABCD


def check(N, M, Q, ABCD, x):
    score = 0
    for a, b, c, d in ABCD:
        if x[b-1] - x[a-1] == c:
            score += d
    return score


def solve(N, M, Q, ABCD):
    smax = 0
    for a in range(1, M+1):
        for b in range(a, M+1):
            for c in range(b, M+1):
                for d in range(c, M+1):
                    for e in range(d, M+1):
                        for f in range(e, M+1):
                            for g in range(f, M+1):
                                for h in range(g, M+1):
                                    for i in range(h, M+1):
                                        for j in range(i, M+1):
                                            s = check(N, M, Q, ABCD, [a, b, c, d, e, f, g, h, i, j][:N])
                                            smax = max(s, smax)
    return smax


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("{}".format(outputs))

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

L =  [list(map(int,input().split())) for _ in range(q)]
com = list(combinations_with_replacement([i for i in range(1, m+1)], n))

ans = 0
for co in com:
    total = 0
    for a, b, c, d in L:
        if co[b-1] - co[a-1] == c:
            total += d
    ans = max(ans, total)
print(ans)

Submission status: Accepted

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

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

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

ans = -1
for c in C:
    score = 0
    for x in X:
        if (c[x[1] - 1] - c[x[0] - 1]) == x[2]:
            score += x[3]
    if ans < score:
        ans = score

print(ans)

Submission status: Accepted

Solution code:
n, m, q = 0, 0, 0
ABCD = []
ans = 0


def dfs(ns):
    global ans

    A = [int(c) for c in ns.split()]
    if len(A) == n:
        s = 0
        for qi in range(q):
            a, b, c, d = ABCD[qi]
            if A[b - 1] - A[a - 1] == c:
                s += d

        ans = max(s, ans)
        return

    for i in range(A[-1], m + 1):
        dfs('{} {}'.format(ns, str(i)))


def main():
    global n, m, q, ABCD
    n, m, q = [int(e) for e in input().split()]
    ABCD = [[int(e) for e in input().split()] for i in range(q)]

    for mi in range(1, m + 1):
        dfs(str(mi))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
a,b,c=map(int,input().split())
li=list(range(1,b+1))

i=0
list2=[]
list1=[list(map(int,input().split())) for i in range(c)]
max=0
for v in  itertools.combinations_with_replacement(li,a):
    lv=list(v)
    sum1=0


    for i in list1:

        if lv[i[1]-1]-lv[i[0]-1]==i[2]:
            #print(lv)
            #print(i)
            sum1+=i[3]


    if max<=sum1:
        max=sum1


print(max)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import permutations, combinations, combinations_with_replacement

# balls = [1,2,3]
#print(list(permutations(balls, 2))) #順列
#print(list(combinations(balls, 2))) #組み合わせ

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)

ans = 0
nums = range(1, m + 1)

for retsu in combinations_with_replacement(nums, n):
    # print(retsu)
    point = 0
    for i in range(q):
        if retsu[b[i] - 1] - retsu[a[i] - 1] == c[i]:
            point += d[i]
            # print(retsu)
    if ans < point:
        # print(retsu)
        ans = point

print(ans)

Submission status: Accepted

Solution code:
import sys

N, M, Q = map(int, sys.stdin.readline().strip().split())
con = []  # condition
for i in range(Q):
    con.append(list(map(int, sys.stdin.readline().strip().split())))

dig = N + 1  # dig -1 桁の数字を作る
A = [1] * dig
point = 0


def make(min=1, digit=1):
    global point
    for i in range(min, M + 1):
        A[digit] = i
        if digit != dig - 1:
            make(min=i, digit=digit + 1)
        else:
            temp_point = 0
            for c in con:
                if A[c[1]] - A[c[0]] == c[2]:
                    temp_point += c[3]
            point = max(point, temp_point)


for i in range(1, M + 1):
    make(min=i, digit=1)

print(point)

Submission status: Accepted

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

ans = 0
for x in itertools.combinations_with_replacement(range(1,M+1),N):
  score = 0
  x1 = sorted(x)
  score = sum(y[3] for y in list1 if x1[y[1]-1]-x1[y[0]-1] == y[2])
  if score > ans:
    ans = score

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

data = []
for i in range(q):
    data.append(list(map(int, input().split())))

# Aは,1からmまでの整数からn個選ぶ重複組み合わせ
a_list = list(itertools.combinations_with_replacement(range(1,m+1), n))

tokuten_list = []
for a in a_list:
    tokuten = 0
    for q_kumi in data:
        if a[q_kumi[1]-1]-a[q_kumi[0]-1] == q_kumi[2]:
            tokuten += q_kumi[3]
    tokuten_list.append(tokuten)

print(max(tokuten_list))

Submission status: Accepted

Solution code:
import itertools
from collections import defaultdict

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


seq = list(range(1, M+1))
dlist = defaultdict(list)
dres  = defaultdict(int)
Na    = 0

for i,v in enumerate(itertools.combinations_with_replacement(seq, N)):
    dlist[i] = v
    Na += 1


for i in range(Q):
    ai, bi, ci, di = map(int, input().split())
    for j in range(Na):
        tmp = dlist[j]
        if tmp[bi-1] - tmp[ai-1] == ci:
            dres[j] += di
print(max([dres[i] for i in range(Na)]))

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

ans = 0
for A in combinations_with_replacement(range(1, m+1), n):
    s = sum(d for a, b, c, d in req if A[b-1] - A[a-1] == c)
    ans = max(ans, s)
print(ans)

Submission status: Accepted

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

import itertools
data = []
nums = [i for i in range(m)]
for balls in itertools.combinations_with_replacement(nums, n):
    data.append(balls)

#print(data)

qa = []
for i in range(q):
    qa.append(list(map(int,input().split())))
    
ans = 0
for i in data:
    si = 0
    for j in qa:
        if (i[j[1]-1]-i[j[0]-1]) == j[2]:
            si += j[3]
    ans = max(si,ans)
print(ans)

Submission status: Accepted

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

L = []
for i in range(1, 11):
    for j in range(i, 11):
        for k in range(j, 11):
            for l in range(k, 11):
                for m in range(l, 11):
                    for n in range(m, 11):
                        for p in range(n, 11):
                            for q in range(p, 11):
                                for r in range(q, 11):
                                    for s in range(r, 11):
                                        L.append([i, j, k, l, m, n, p, q, r, s])
mm = 0
X = [list(map(int, input().split())) for _ in range(Q)]
for i in L:
    if i[N-1] <= M:
        S = i[:]
        SS = 0
        for j in X:
            if S[j[1]-1] - S[j[0]-1] == j[2]:
                SS += j[3]
        if mm < SS:
            mm = SS
print(mm)

Submission status: Accepted

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

import itertools
anses = []
# for A in itertools.product(sum(([i]*n for i in range(1,m+1)),[]), repeat=n):
# for A in itertools.product(range(1, m + 1), repeat=n):

def f(A):
  for ai in range(A[-1], m + 1):
    if len(A) < n:
      f(A + [ai])
    else:
      p = 0
      for a, b, c, d in abcd:
        a -= 1
        b -= 1
        if A[b] - A[a] == c:
          p += d
      anses.append(p)

f([1])
print(max(anses))

Submission status: Accepted

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

N=0
M=0

def next_num(x):
    if int(x[-1]) < M:
        return x[:-1] + [str(int(x[-1]) + 1)]
    elif int(x[-1]) == M:
        oya = next_num(x[:-1])
        return oya + [oya[-1]]


def solve(N: int, M: int, Q: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
    start = ['1' for i in range(N)]
    current = start
    ans = 0
    while True:
        result = 0
        for a_, b_, c_, d_ in zip(a, b, c, d):
            if int(current[b_]) - int(current[a_]) == c_:
                result += d_
        if result > ans:
            ans = result
        if current[0] == str(M):
            break
        current = next_num(current)
    print(ans)
    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():
    global N, M
    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)) - 1
        b[i] = int(next(tokens)) - 1
        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 = map(int,input().split())
A = []
for _ in range(Q):
    a = list(map(int,input().split()))
    A.append(a)
import itertools
m=[]
for i in range(1,M+1):
    m.append(i)
list_ = list(itertools.combinations_with_replacement(m,N))
answers = []
for l in list_:
    ans = 0
    for a in A:
        if l[a[1]-1]-l[a[0]-1] == a[2]:
            ans += a[3]
    answers.append(ans)
print(max(answers))

Submission status: Accepted

Solution code:
import itertools

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

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

tans = 0
ans = 0

for A in listA:
  flg = 0
  for i in range(1,len(A)):
    if A[i-1] > A[i]:
      flg = 1
      break
  if flg == 0:
    tans = 0
    for i in range(Q):
      if A[b[i]-1]-A[a[i]-1] == c[i]:
        tans += d[i]
    if tans>ans:
      ans = tans
print(ans)

Submission status: Accepted

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

for i_1 in range(1, M + 1):
    for i_2 in range(i_1, M + 1):
        for i_3 in range(i_2, M + 1):
            for i_4 in range(i_3, M + 1):
                for i_5 in range(i_4, M + 1):
                    for i_6 in range(i_5, M + 1):
                        for i_7 in range(i_6, M + 1):
                            for i_8 in range(i_7, M + 1):
                                for i_9 in range(i_8, M + 1):
                                    for i_10 in range(i_9, M + 1):
                                        A_s_cand.append([i_1, i_2,i_3,i_4,i_5,i_6,i_7,i_8,i_9,i_10])
                                        
                                        
A_s = []
for a in A_s_cand:
    A_s.append(a[:N])

ans_cand = []
for a in A_s:
    ans = 0
    if len(a) <= N:
        for i in abcd:
            if a[i[1] - 1] == a[i[0] - 1] + i[2]:
                ans += i[3]
        ans_cand.append(ans)

print(max(ans_cand))

Submission status: Accepted

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

number_list = [int(i) for i in range(1,M+1)]
comb_number_list = list(itertools.combinations_with_replacement(number_list,N))
Q_list_total = []

for i in range(Q):
    Q_list = [int(x) for x in input().split()]
    Q_list_total.append(Q_list)
#print(Q_list_total)    
    
#print(comb_number_list)
answer_list = []

for i in range(len(comb_number_list)):
    answer = 0
    total = 0
    for j in range(len(Q_list_total)):
        answer = comb_number_list[i][Q_list_total[j][1]-1] - comb_number_list[i][Q_list_total[j][0]-1]
        if answer == Q_list_total[j][2]:
            total += Q_list_total[j][3]
    answer_list.append(total)
#print(Q_list)
print(max(answer_list))

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

n, m, q = MAP()
arr = [[]]
for i in range(n):
    tmp = deepcopy(arr)
    arr = []
    for j in range(1, m + 1):
        for k in range(len(tmp)):
            if len(tmp[k]) == 0 or tmp[k][-1] <= j:
                arr.append(deepcopy(tmp[k]))
                arr[-1].append(j)

point = [0 for _ in range(len(arr))]
for i in range(q):
    a, b, c, d = MAP()
    for j in range(len(arr)):
        if arr[j][b - 1] - arr[j][a - 1] == c:
            point[j] += d
#print(point)
print(max(point))

Submission status: Accepted

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

max_score = 0

p = [1] * n
cur = n-1
while cur >= 0:
    score = 0
    for a, b, c, d in queries:
        if p[b - 1] - p[a - 1] == c:
            score += d
    max_score = max(score, max_score)
    updated = False
    for i in range(n - 1, -1, -1):
        if p[i] != m:
            p[i] += 1
            for j in range(i + 1, n):
                p[j] = p[i]
            updated = True
            break
    if not updated:
        break

print(max_score)

Submission status: Accepted

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

# -- submit ----

import itertools

# --- fetch input ---
inputs: list = []
while True:
    try:
        inputs.append(input().strip('\n'))
    except EOFError:
        break

# --- write code below ---
n, m, q = (int(i) for i in inputs[0].split())
conditions = [[int(j) for j in c.split()] for c in inputs[1:]]

# length == n -> break
candidates: list = []

results = itertools.combinations_with_replacement(range(1, m+1), n)
for i in results:
    temp_sum = 0
    for con in conditions:
        a, b, c, d = con
        if i[b-1] - i[a-1] == c:
            temp_sum += d
    if temp_sum > 0:
        candidates.append(temp_sum)

ranking = sorted(candidates)
print(ranking[-1])

Submission status: Accepted

Solution code:
N,M,Q = map(int,input().split())
q = []
for i in range(Q):
	a,b,c,d = map(int,input().split())
	q.append((a-1,b-1,c,d))

def score(ary):
	ret = 0
	for x in q:
		if ary[x[1]] - ary[x[0]] == x[2]:
			ret += x[3]
	return ret

def f(n,mi,ary):
	if n == 0:
		return score(ary)
	return max([f(n-1, i, ary + [i]) for i in range(mi, M+1)])

print(f(N-1, 1, [1]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def input(): return sys.stdin.readline().rstrip()

import itertools

def main():
  N, M, Q = map(int, input().split())
  all_num = [i for i in range(1, M+1)]
  q_kumi = []
  for i in range(Q):
    q_kumi.append(list(map(int, input().split())))

  ans = 0
  for com in list(itertools.combinations_with_replacement(all_num, N)):
    tmp_ans = 0
    if com != tuple(sorted(com)):
      continue
    for q in q_kumi:
      if com[q[1]-1] - com[q[0]-1] == q[2]:
        tmp_ans += q[3]
    ans = max(ans, tmp_ans)
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Accepted

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

def nextlist(A):
    for i in range(A[-1],M+1):
        yield A+[i]

X=[[1]]
for rep in range(N-1):
    NX=[]
    for x in X:
        NX.extend(nextlist(x))
    X=NX

ANS=0
for x in X:
    score=0
    for a,b,c,d in SC:
        if x[b-1]-x[a-1]==c:
            score+=d
    ANS=max(ANS,score)

print(ANS)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

candi = []
N, M, Q = map(int, readline().split())

def pp(res, i, j):
    rr = res + [i]
    if j == 0:
        candi.append(res)
        return 
    else:
        for st in range(i, M+1):
            pp(rr, st, j-1)

for i in range(1, M+1):
    pp([], i, 10)


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

ans = 0
for k in candi:
    res = 0
    for a, b, c, d in ABCD:
        if k[b-1] - k[a-1] == c:
            res += d
    ans = max(res, ans)
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
def solve(list):
    lis = []
    for x in list:
        n = x[-1]
        for i in range(n, M+1):
            a = deepcopy(x)
            a.append(i)
            lis.append(a)
    return lis


N, M, Q = map(int, input().split())
li  = []
q = []
for i in range(Q):
    q.append(list(map(int, input().split())))
for i in range(M):
    li.append([i+1])
for i in range(N-1):
    li = solve(li)
m = 0
for x in li:
    cnt = 0
    for y in q:
        [a,b,c,d] = y
        if x[b-1] - x[a-1] == c:
            cnt += d
    m = max(m, cnt)
print(m)

Submission status: Accepted

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

# 全探索
ans = 0
for i, comb in enumerate(combinations(range(n+m-2), r=n-1)):
    # 数列の構成
    A = [1] * n
    idx = 0
    for i in range(n+m-2):
        if i in comb:
            idx += 1
            A[idx] = A[idx-1]
        else:
            A[idx] += 1

    # クエリの判定
    score = 0
    for query in queries:
        a, b, c, d = query
        if A[b] - A[a] == c:
            score += d
    ans = max(ans, score)

print(ans)

Submission status: Accepted

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

for A_9 in range(1,M + 1):
  for A_8 in range(1,A_9 + 1):
    for A_7 in range(1,A_8 + 1):
      for A_6 in range(1,A_7 + 1):
        for A_5 in range(1,A_6 + 1):
          for A_4 in range(1,A_5 + 1):
            for A_3 in range(1,A_4 + 1):
              for A_2 in range(1,A_3 + 1):
                for A_1 in range(1,A_2 + 1):
                  A = [A_1,A_2,A_3,A_4,A_5,A_6,A_7,A_8,A_9,M]
                  d = 0
                  for i in range(Q):
                    a = Query[i][0] - 1
                    b = Query[i][1] - 1
                    if A[b] - A[a] == Query[i][2]:
                      d += Query[i][3]
                      if d > MAX:
                        MAX = d         
      
      
           
print(MAX)

Submission status: Accepted

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

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

l_tensu = 0
for subset in itertools.combinations_with_replacement(A_full, N):
    tensu = 0

    A = list(subset)
    for i in range(Q):
        a = List[i][0] - 1
        b = List[i][1] - 1
        c = List[i][2]
        d = List[i][3]
        if (A[b] - A[a] == c):
            tensu += d
    if(tensu > l_tensu):
        l_tensu = tensu
    
print(l_tensu)

Submission status: Accepted

Solution code:
import itertools

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

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

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

max_score = 0
for a in itertools.combinations_with_replacement(A,N):
	score = 0
	for s in series:
		if (a[s[1]-1] - a[s[0]-1]) == s[2]:
			score += s[3]

	if score > max_score: max_score = score

print(max_score)

Submission status: Accepted

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

for i in range(Q):
  aa, bb, cc, dd = list(map(int, input().split()))
  a.append(aa)
  b.append(bb)
  c.append(cc)
  d.append(dd)

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


res = 0
for s in itertools.combinations_with_replacement(Ms, N):
  sum_ = 0
  for j in range(Q):
    if s[b[j]-1] - s[a[j]-1] == c[j]:
      sum_ += d[j]
  if sum_ > res:
    res = sum_

print(res)

Submission status: Accepted

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


def check(arr):
    num = 0
    for e in A:
        if arr[e[1]-1] - arr[e[0]-1] == e[2]:
            num += e[3]

    # print(arr, num)
    return num


def dfs(idx):
    # print(idx, B)
    if idx == -1:
        res = check(B)
        max_res[0] = max(max_res[0], res)

    else:
        prev = B[idx+1] if idx != n-1 else m
        for j in range(1, prev+1):
            B[idx] = j
            dfs(idx-1)

B = [0]*n
max_res = [0]
dfs(n-1)

print(max_res[0])

Submission status: Accepted

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

def C():
    N, M, Q = map(int, input().split())
    ans = 0
    possibles = []
    def generate(cur_list, last):
        if len(cur_list) == N:
            possibles.append(cur_list)
            return
        for j in range(last, M+1):
            generate(cur_list+[j], j)

    generate([], 1)

    D = [0 for i in range(len(possibles))]

    # print(possibles)
    for i in range(Q):
        a, b, c, d = map(int, input().split())
        for i, p in enumerate(possibles):
            if p[b-1] - p[a-1] == c:
                D[i] += d
    
    print(max(D))

C()

Submission status: Accepted

Solution code:
import itertools

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

m_li = []
for i in range(1,m+1):
    m_li.append(i)

li = []
mx = 0

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

for v in itertools.combinations_with_replacement(m_li,n):
    buf = 0
    for i in range(q):
        a = li[i][0]
        b = li[i][1]
        c = li[i][2]
        d = li[i][3]
        if v[b-1] - v[a-1] == c:
            buf += d
    if buf >= mx:
        mx = buf

print(mx)

Submission status: Accepted

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

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

def check(ls):
    count = 0
    for i in range(Q):
        if ls[req[i][1] - 1] - ls[req[i][0] - 1] == req[i][2]:
            count += req[i][3]
    return count

for a in lists:
    s = check(a)
    if s > ans:
        ans = s

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

l=[]
for v in itertools.combinations_with_replacement(list(range(1,m+1)), n):
    l.append(list(v))

for i in l:
    ans1=0
    for j in range(q):
        ans1+=lis[j][3]*((i[lis[j][1]-1]-i[lis[j][0]-1])==lis[j][2])
    ans=max(ans,ans1)
print(ans)

Submission status: Accepted

Solution code:
import bisect,sys
import math
from collections import deque

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29

DIV = (10**9) + 7

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac =fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV
        
    return CONV()



sys.setrecursionlimit(200005)


def main():
    N,M,Q = isRaw()
    abcds = [isRaw() for m in range(Q)]
    def dfs(As):
        if len(As)==N:
            cur = 0
            for abcd in abcds:
                a,b,c,d = abcd
                if As[b-1]-As[a-1] == c:
                    cur+=d
            return cur 
        tmp = 0
        for a in range(As[-1],M+1):
            tmp = max(dfs(As+[a]),tmp)
        return tmp
    return dfs([1])
    
if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
import itertools

x = input().split(' ')
n = int(x[0])
m = int(x[1])
q = int(x[2])

abcd = []

for i in range(q):
  x = input().split(' ')
  tmp = []
  for j in range(4):
    tmp.append(int(x[j]))
    
  abcd.append(tmp)
  

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

score = 0

for candidate in a_candidates:
  score_tmp = 0
  for abcd_ in abcd:
    a = abcd_[0]-1
    b = abcd_[1]-1
    c = abcd_[2]
    d = abcd_[3]
    
    if (candidate[b]-candidate[a]) == c:
      score_tmp += d
      

  if score_tmp > score:
    score = score_tmp
    
print(score)