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 sys
sys.setrecursionlimit(300000)
from itertools import combinations_with_replacement
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, M, Q = MI()
ABCD = [tuple(MI()) for i in range(Q)]

ans = 0
for arr in combinations_with_replacement(range(1, M + 1), N):
    A = list(arr)
    score = 0
    for a, b, c, d in ABCD:
        if A[b - 1] - A[a - 1] == c:
            score += d
    ans = max(ans, score)
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

nums = [x for x in range(1, m+1)]
num_list = list(itertools.combinations_with_replacement(nums, n))

result_lst = []
for num in num_list:
    result = 0
    for i in abcd:
        a, b, c, d = i[0], i[1], i[2], i[3]
        x = num[b-1] - num[a-1]
        if x == c:
            result += d
    result_lst.append(result)
print(max(result_lst))

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

q_list = []
for _ in range(Q):
    a, b, c, d = input().split()
    q_list.append([int(a), int(b), int(c), int(d)])

max_pts = 0
for A in combinations_with_replacement(range(1, M + 1), N):
    pts = 0
    for (a, b, c, d) in q_list:
        if A[b - 1] - A[a - 1] == c:
            pts += d
    max_pts = max(max_pts, pts)

print(max_pts)

Submission status: Accepted

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


def main(l, m):
    ret = 0
    if len(l) == N:
        for a, b, c, d in L:
            if l[b - 1] - l[a - 1] == c:
                ret += d
        return ret

    for i in range(m, M + 1):
        ret = max(ret, main(l + [i + 1], i))
    return ret


print(main([], 1))

Submission status: Accepted

Solution code:
import itertools
N, M, Q = map(int, input().split())
a = [list(map(int, input().split())) for l in range(Q)]
b = [1]*N
c = 0
for i in range(Q):
  if b[a[i][1]-1]-b[a[i][0]-1] == a[i][2]:
    c += a[i][3]
C = c
for k in range(1,M):
  nums = [i for i in range(N-1)]
  for balls in itertools.combinations_with_replacement(nums, k):
    b = [1]*N
    c = 0
    for i in range(1,N):
      b[i] = b[i-1] + balls.count(i-1)
    for i in range(Q):
      if b[a[i][1]-1]-b[a[i][0]-1] == a[i][2]:
        c += a[i][3]
    C = max(C,c)
print(C)

Submission status: Accepted

Solution code:
n,m,q = map(int,input().split())
a = [[int(i) for i in input().split()] for _ in range(q)]
b = []
for i in range(m):
    b.append(i+1)
import itertools
l = list(itertools.combinations_with_replacement(b,n))
max=0
#print(l)                                                                      
for ll in l:
    m=0
    for aa in a:
        if ll[aa[1]-1]-ll[aa[0]-1]==aa[2]:
            m+=aa[3]
    if max < m:
        max=m
print(max)

Submission status: Accepted

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

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

def get_next(l):
	i = n-1
	while i > -1 and l[i] == m:
		i -= 1

	if i < 0:
		return -1
	else:
		l[i] += 1
		for j in range(i+1, n):
			l[j] = l[i]
	return l

max_score = 0
cur_seq = [1 for _ in range(n)]
while cur_seq != -1:
	cur_score = 0
	for i in range(q):
		if cur_seq[b[i]] - cur_seq[a[i]] == c[i]:
			cur_score += d[i]
	if cur_score > max_score:
		max_score = cur_score
	cur_seq = get_next(cur_seq)

print(max_score)

Submission status: Accepted

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

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

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

import itertools

ans = 0

for v in itertools.combinations_with_replacement(l, N):
    answ = 0
    make = 1
    for i in range(Q):
        if v[abcd[i][1]-1] - v[abcd[i][0]-1] == abcd[i][2]:
            answ += abcd[i][3]
    ans = max(ans,answ)
        
print(ans)

Submission status: Accepted

Solution code:
import itertools

n, m, q = map(int, input().split())
abcd = []
for i in range(q):
    abcd.append(list(map(int, input().split())))
ans = 0
j = [0] * 10
for i1 in range(1, m + 1):
    j[0] = i1
    for i2 in range(i1, m + 1):
        j[1] = i2
        for i3 in range(i2, m + 1):
            j[2] = i3
            for i4 in range(i3, m + 1):
                j[3] = i4
                for i5 in range(i4, m + 1):
                    j[4] = i5
                    for i6 in range(i5, m + 1):
                        j[5] = i6
                        for i7 in range(i6, m + 1):
                            j[6] = i7
                            for i8 in range(i7, m + 1):
                                j[7] = i8
                                for i9 in range(i8, m + 1):
                                    j[8] = i9
                                    for i10 in range(i9, m + 1):
                                        j[9] = i10
                                        temp = 0
                                        for i in range(q):
                                            if j[abcd[i][1] - 1] - j[abcd[i][0] - 1] == abcd[i][2]:
                                                temp += abcd[i][3]
                                        ans = max(ans, temp)
print(ans)

Submission status: Accepted

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

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

cond.sort()
#print(cond)
finalres = 0
dat = [1] * n
while True:
    for i in range(n - 1, -1, -1):
        if dat[i] > m:
            dat[i] = dat[i - 1]
            dat[i - 1] += 1
        else:
            break
    ispass = False
    for i in range(n - 1, 0, -1):
        if dat[i] < dat[i - 1]:
            ispass = True
            break
    if ispass:
        dat[n - 1] += 1
        if dat[0] >= m:
            break
        continue

    #print("Try:", dat)

    can = True
    res = 0
    for i in range(q):
        a, b, c, d = cond[i]
        a, b = a-1, b-1
        if dat[b] - dat[a] == c:
            #print(" > match i{0} -i{1} == c gain {2}".format(b, a, d))
            res += d
    finalres = max(finalres, res)

    dat[n - 1] += 1
    if dat[0] >= m:
        break
print(finalres)

Submission status: Accepted

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n, m, q = map(int, args[0].split())
    ABCD = [tuple(map(int, abcd.split())) for abcd in args[1:]]

    ret = 0
    stack = [(i, '') for i in range(10)]
    while stack:
        t, s = stack.pop()
        S = s+str(t)
        if len(S) == n:
            ret = max(
                ret,
                sum([d for a, b, c, d in ABCD if int(S[b-1])-int(S[a-1]) == c])
            )
            continue

        for i in range(t, m):
            stack.append((i, S))

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

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

A = [1]*(N+1)
res = 0
def f(n):
    global res
    if n == N+1:
        res = max(f2(), res)
        return
    for i in range(A[n-1], M+1):
        A[n] = i 
        f(n+1)
    return res

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

f(1)
print(res)

Submission status: Accepted

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

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

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

a_max = 0
for a in a_list:
    d_cnt = 0
    for q_v in q_list:
        if q_v[1] > len(a):
            continue
        if a[q_v[1] - 1] - a[q_v[0] - 1] == q_v[2]:
            d_cnt += q_v[3]

    if a_max < d_cnt:
        a_max = d_cnt

print(a_max)

Submission status: Accepted

Solution code:
from itertools import product as prd
n, m, q = map(int, input().split())
Jyoken = []

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

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

for i in range(n - 1):
    temp = []
    for pattern in patterns:
        matsubi = pattern[-1]
        for num in range(matsubi, m + 1):
            temp.append(pattern + [num])
    patterns = temp

#print(patterns)

max_point = 0
for A in patterns:
    point = 0
    for rule in Jyoken:
        a, b, c, d = rule
        if A[b] - A[a] == c:
            point += d
    max_point = max(point, max_point)
print(max_point)

Submission status: Accepted

Solution code:
import itertools
N,M,Q=map(int,input().split())
ali=list(itertools.combinations_with_replacement(range(1,M+1),N))
mat=[list(map(int,input().split())) for i in range(Q)]
ali=list(sorted(ali))
anlist=[0]*len(ali)
l=0
for i in ali:
  for j in mat:
    a=j[1]-1
    b=j[0]-1
    if i[a]-i[b]==j[2]:
      anlist[l]+=j[3]
  l+=1
print(max(anlist))

Submission status: Accepted

Solution code:
N, M, Q = [int(i) for i in input().split(" ")]
ans = 0
que = [1 for i in range(1, N+1)]
a=[0]*Q
b=[0]*Q
c=[0]*Q
d=[0]*Q
for i in range(Q):
    a[i], b[i], c[i], d[i] = [int(j) for j in input().split(" ")]

while True:
    if len(que) == N:
        s=0
        for i in range(Q):
            if que[b[i]-1] - que[a[i]-1] == c[i]:
                s += d[i]
        ans = max(ans, s)
    n = que.pop()
    if n < M:
        for i in range(N):
            que.append(n+1)
            if len(que) == N:
                break
    if len(que) == 0:
        break

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

A = [[ int(n) for n in input().split()] for _ in range(Q) ]
n = [i for i in range(1,M+1)]
numbers = list(itertools.combinations_with_replacement(n, N))
ans = [0 for _ in range(len(numbers))]

q = Q
while  q> 0:
    q -= 1
    a, b, c, d = A[q][0], A[q][1], A[q][2], A[q][3]

    for i in range(len(numbers)):
        if numbers[i][b-1] - numbers[i][a-1] == c:
            ans[i] += d


print(max(ans))

Submission status: Accepted

Solution code:
import itertools

N, M, Q = map(int, input().split())
comb = list(itertools.combinations_with_replacement(range(1,M+1), N))

ans = [0]*len(comb)
if ans == []:
    print(0)
else:
    for i in range(Q):
        a,b,c,d = map(int, input().split())
        for j in range(len(comb)):
            if comb[j][b-1] - comb[j][a-1] == c:
                ans[j] += d
    print(max(ans))

Submission status: Accepted

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

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

max_val = 0
for A in As:
    val = 0
    for abcd in data:
        if A[abcd[1]-1] - A[abcd[0]-1] == abcd[2]:
            val += abcd[3]
    if val > max_val:
        max_val = val

print(max_val)

Submission status: Accepted

Solution code:
N,M,Q = map(int,input().split())
ABCD = []
for q in range(Q):
    ABCD.append([int(i) for i in input().split()])
from itertools import combinations_with_replacement as comb
M_list = [i for i in range(1,M+1)]
ans = 0
for c in comb(M_list,N):
    temp = 0
    for abcd in ABCD:
        if c[abcd[1]-1] - c[abcd[0]-1] == abcd[2]:
            temp += abcd[3]
    ans = max(temp,ans)
print(ans)

Submission status: Accepted

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

import itertools
l = range(1, m+1)
sums = [0]
for v in itertools.combinations_with_replacement(l, n):
  v = list(v)
  sum = 0
  for a, b, c, d in tokutens:
    if v[int(b)-1] - v[int(a)-1] == int(c):
      sum+=int(d)
  sums.append(sum)

sums.sort(reverse=True)
print(sums[0])

Submission status: Accepted

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

A = list(itertools.combinations_with_replacement(range(1, M + 1), N))
ans = 0
for a in A:
    tmp = 0
    for l in L:
        if a[l[1] - 1] - a[l[0] - 1] == l[2]:
            tmp += l[3]
    else:
        ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
def main():
    from itertools import combinations_with_replacement
    n, m, q, *abcd = map(int, open(0).read().split())

    x = zip(*[iter(abcd)] * 4)

    x = list(x)

    y = range(1, m + 1)
    ans = 0
    for v in combinations_with_replacement(y, n):
        temp = 0
        v = list(v)
        v.sort()
        for (a, b, c, d) in x:
            if v[b - 1] - v[a - 1] == c:
                temp += d

        ans = max(ans, temp)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

 
input_line = input()
Line = input_line.split()
Line = [int(s) for s in Line]
N,M,Q = Line[0],Line[1],Line[2]

l = list(range(1, M+1))

# print(l)

q_list = []

for _ in range(Q):
    input_line = input()
    Line = input_line.split()
    Line = [int(s) for s in Line]
    q_list.append(Line)

p_list = list(itertools.combinations_with_replacement(l, N))

max_point = 0

for i in p_list:
    # print(i)
    now_point = 0
    for x in q_list:
        # print("-------", x)
        if i[x[1]-1] - i[x[0]-1] == x[2]:
            now_point += x[3]
            # print(now_point)
    if now_point > max_point:
        max_point = now_point
    # print(max_point,now_point)
print(max_point)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

scores = []
for A in combinations_with_replacement(range(1, M + 1), N):
    score = 0
    for t in ts:
        a, b, c, d = t
        if A[b - 1] - A[a - 1] == c:
            score += d
    scores.append(score)

print(max(scores))

Submission status: Accepted

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

ans=0
A=[1]*(N+1)
while True:
    tmp=0
    for a,b,c,d in ABCD:
        if A[b]-A[a]==c: tmp+=d
    ans = max(ans, tmp)
    up=1
    for i in range(N,0,-1):
        A[i]+=up
        if A[i]>M:
            up=1
            A[i]=M
        else:
            up=0
            for j in range(i+1,N+1):
                A[j]=A[i]
            break
    if up==1: break
print(ans)

Submission status: Accepted

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

def dfs(nn,anni,vmax):
    if nn==n:
        qsum=0
        for j in range(q):
#            print(j,abcd[j][1],abcd[j][0])
            if a[abcd[j][1]-1]-a[abcd[j][0]-1]==abcd[j][2]:
                qsum=qsum+abcd[j][3]
#        print(qsum,a)
        return qsum
    a[nn]=anni
#    vmax=0
    for i in range(10):
        if a[nn]+i<=m:
            v=dfs(nn+1,a[nn]+i,vmax)
            vmax=max(v,vmax)
    return vmax

vmax=0
a=[0]*n
print(dfs(0,1,vmax))

Submission status: Accepted

Solution code:
from copy import deepcopy

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

high_score = 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):
                                        score = 0
                                        A = [a,b,c,d,e,f,g,h,i,j]
                                        for li in l:
                                            if A[li[1]-1]-A[li[0]-1] == li[2]:
                                                score += li[3]
                                            if(high_score < score):
                                                high_score = score
print(high_score)

Submission status: Accepted

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

xs = []
for i in range(q):
    a1,b1,c1,d1 = map(int,input().split())
    xs.append([a1,b1,c1,d1])


cnt = 0
for a in range(1,11):
    for b in range(a,11):
        for c in range(b,11):
            for d in range(c,11):
                for e in range(d,11):
                    for f in range(e,11):
                        for g in range(f,11):
                            for h in range(g,11):
                                for i in range(h,11):
                                    for j in range(i,11):
                                        ass = [a,b,c,d,e,f,g,h,i,j]
                                        if ass[n-1] > m:
                                            break
                                        else:
                                            s = 0
                                            for k in range(q):
                                                if ass[xs[k][1] - 1] - ass[xs[k][0] - 1] == xs[k][2]:
                                                    s += xs[k][3]
                                        if s >= cnt:
                                            cnt = s


print(cnt)

Submission status: Accepted

Solution code:
import sys,itertools
input = sys.stdin.readline


n,m,q = map(int,input().split())
seq = list(range(n+m-1))
p = list(itertools.combinations(seq,n))

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

#print(p)

res = 0
for i in range(len(p)):
    t = [0]*n
    pp = sorted(p[i])
    idx = 0
    for e in pp:
        t[idx] = 1+e-idx
        idx += 1
    
    tmp = 0
    for j in range(q):
        if t[b[j]-1] - t[a[j]-1] == c[j]:
            tmp += d[j]
    
    res = max(res,tmp)

print(res)

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

answer = 0

nums=[]
for i in range(1, M+1):
    nums.append(i)

for balls in itertools.combinations_with_replacement(nums, N):
    score = 0
    test = list(balls)
    for i in range(Q):
        if test[abcd[i][0]-1] + abcd[i][2] == test[abcd[i][1]-1]:
            score += abcd[i][3]
    if score > answer:
        answer = score

print(answer)

Submission status: Accepted

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

que=[[1]]
while len(que)!=0:
    now=que.pop(0)
    last=now[-1]
    #print(now)
    for next_n in range(last, M+1):
        if len(now)+1==N:
            L.append(now+[next_n])
        else:
            que.append(now+[next_n])

ans=0
for A in L:
    sub=0
    for j in range(Q):
        a,b,c,d=G[j]
        
        if A[b-1]-A[a-1]==c:
            sub+=d
        #print(sub)
    ans=max(ans, sub)

print(ans)

Submission status: Accepted

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

def sum_d(l):
    s = 0
    for a,b,c,d in Qs:
        if l[b] - l[a] == c:
            s += d
    return s


def f(l,ans):
    if len(l) == N:
        s = sum_d(l)
        return s
    
    if len(l) == 0:
        pre = 0
    else:
        
        pre = l[-1]

    for i in range(1,M+1):
        if i < pre:
            continue
        ret = f(l+[i],ans)
        if ret > ans:
            ans = ret
    
    return ans


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

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

# abcd.sort(key=lambda x:x[3],reverse=True)
# for x in abcd:
#     print("")
#     for v in x:
#         print(v,end=" ")
arr = [i for i in range(1,m+1)]

ans = 0
for per in itertools.combinations_with_replacement(arr,n):

    tmp = 0
    for x in abcd:
        diff = per[x[1]-1] - per[x[0]-1]
        if(diff == x[2]):
            tmp += x[3]
    # print(per,end=" ")
    # print(tmp)
    ans = max(ans,tmp)

print(ans)

Submission status: Accepted

Solution code:
import itertools

def main():
    m = 100
    n, m, q = input_list()
    queries = []
    for _ in range(q):
        queries.append(input_list())
    a = []
    for i in range(1, m+1):
        a.append(i)
    ans = []
    for i in itertools.combinations_with_replacement(a, n):
        ans.append(calc(i, queries))
    print(max(ans))


def calc(i, queries):
    ans = 0
    for q in queries:
        a, b, c, d = q
        if i[b-1] - i[a-1] == c:
            ans += d
    #print(i, ans)
    return ans

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m, q = map(int, input().split())
L = [1]
ans = 0

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


def gen(i):
    global ans
    if len(L) == n:
        cc = 0
        for a, b, c, d in D:
            if L[b] - L[a] == c:
                cc += d
        ans = max(ans, cc)
        return
    for x in range(L[-1], m + 1):
        L.append(x)
        gen(i + 1)
        L.pop()


gen(1)
print(ans)

Submission status: Accepted

Solution code:
import copy

N, M, Q = map(int, input().split())
A = [[] for i in range(20)]
for i in range(N):
    if i == 0:
        for j in range(1, M+1):
            A[i].append([j])
    else:
        for j in range(len(A[i-1])):
            for k in range(A[i-1][j][i-1], M+1):
                temp = copy.copy(A[i-1][j])
                temp.append(k)
                A[i].append(temp)

X = []
Y = []
C = []
D = []
for i in range(Q):
    a, b, c, d = map(int, input().split())
    X.append(a-1)
    Y.append(b-1)
    C.append(c)
    D.append(d)

ans = 0
for i in range(len(A[N-1])):
    s = copy.copy(A[N-1][i])
    p = 0
    for q in range(Q):
        if s[Y[q]] - s[X[q]] == C[q]:
            p += D[q]
    ans = max([p, ans])
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m, q = LI()
L = LIR(q)
ans = 0
def f(arr):
    global ans
    if len(arr) == n:
        ret = 0
        for a, b, c, d in L:
            if arr[b - 1] - arr[a - 1] == c:
                ret += d
        ans = max(ans, ret)
    else:
        if arr:
            for k in range(arr[-1], m + 1):
                f(arr + [k])
        else:
            for k in range(1, m + 1):
                f(arr + [k])

f([])
print(ans)

Submission status: Accepted

Solution code:
import itertools
k = list(map(int, input().split()))
l = [list(map(int, input().split())) for i in range(k[2])]
m = [i+1 for i in range(k[1])]
n= list(itertools.combinations_with_replacement(m, k[0]))
now = 0
re = 0
for i in n:
  for x in l:
    if i[x[1] -1] - i[x[0] -1] == x[2]:
      re += x[3]
  now = max([now, re])
  re = 0

print(now)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
INF = 10**10
MOD = 10**9 + 7

        



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




old = []
for i in range(1,M+1):
    old.append([i])

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


#print (new)
mx = 0
for n in new:
    score = 0
    for a,b,c,d in query:
        if (n[b] - n[a] == c):
            score += d
    mx = max(score,mx)
print (mx)

Submission status: Accepted

Solution code:
#C
import itertools
N,M,Q=map(int,input().split())
X=[[int(x) for x in input().split()] for i in range(Q)]
IN=[int(i) for i in range(1,M+1)]
Max=0
for com in itertools.combinations_with_replacement(IN, N):
    Sum=0
    for i in range(Q):
        a=int(X[i][0])-1
        b=int(X[i][1])-1
        c=int(X[i][2])
        d=int(X[i][3])
        if com[b]-com[a]==c:
            Sum+=d
    Max=max(Max,Sum)
print(Max)

Submission status: Accepted

Solution code:
N,M,Q=list(map(int,input().split()))
M=[i for i in range(1,M+1)]
import itertools
A=list(itertools.combinations_with_replacement(M, N))
a=[0]*Q
b=[0]*Q
c=[0]*Q
d=[0]*Q
for i in range(Q):
  a[i],b[i],c[i],d[i]=list(map(int,input().split()))
s=[]
ans=0
for j in range(len(A)):
  for k in range(Q):
    if A[j][b[k]-1]-A[j][a[k]-1]==c[k]:
      ans=ans+d[k]
  s.append(ans)
  ans=0
print(max(s))

Submission status: Accepted

Solution code:
N,M,Q=map(int, input().split())
ABCD=[tuple(map(int, input().split()))for _ in range(Q)]
def rec(X):
    ans=0
    if len(X)==N:
        res=0
        for a,b,c,d in ABCD:
            if X[b-1]-X[a-1]==c:
                res+=d
        return res
    s = 1 if len(X)==0 else X[-1]
    for i in range(s,M+1):
        X.append(i)
        ans=max(ans,rec(X))
        X.pop()
    return ans
print(rec([]))

Submission status: Accepted

Solution code:
import itertools
N , M ,Q= map(int,input().split())
seq = list(range(N+M-1))
pattern = list(itertools.combinations(seq,N))
prob_array = []
for i in range(Q):
    a ,b ,c , d = map(int,input().split())
    prob_array.append([a,b,c,d])
    
def convert_number(lst):
    num_ = 1
    lst = list(lst)
    lst.insert(0,-1)
    return_list = []
    for i in range(len(lst) - 1):
        num_ += lst[i+1] - lst[i] - 1
        return_list.append(num_)
    return return_list
    
opt_point = 0
for input_list in pattern:
    judge_list = convert_number(input_list)
    temp_point = 0
    for p_ in prob_array:
        if judge_list[p_[1] - 1] - judge_list[p_[0] - 1] == p_[2]:
            temp_point += p_[3]
    if temp_point >= opt_point:
        opt_point = temp_point
print(opt_point)

Submission status: Accepted

Solution code:
from collections import deque
n, m, q = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(q)]
result = [0]
p = deque([[i] for i in range(1, m+1)])
while p:
    i = p.popleft()
    if len(i) == n:
        r = 0
        for a, b, c, d in x:
            if i[b-1]-i[a-1]==c:
                r += d
        result.append(r)
    else:
        for j in range(i[-1], m+1):
            p.append(i+[j])
print(max(result))

Submission status: Accepted

Solution code:
import itertools

N,M,Q = map(int,input().split())
q = []
ans = 0
c = 0
array = [int(i) for i in range(1,M+1)]

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

def check(A):
    score = 0
    i = 0
    for a,b,c,d in q:
        i += 1
        if A[b-1]-A[a-1] == c:
#            print(a,b,c,d)
            score += d
#    print(i)
    return score

h = itertools.combinations_with_replacement(array, N)
for v in h:
    ans = max(ans,check(v))
#    print(v)

"""
for i in range(2**M):
    len = 0
    A = []
    for j in range(M):
        if (i>>j) & 1:
            len += 1
            A.append(j+1)
    if len == N:
        print(A)
        ans = max(ans,check(A))
"""
print(ans)

Submission status: Accepted

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

import itertools

List = []
for v in itertools.combinations_with_replacement(range(1, m+1), n):
    List.append(list(v))
    
answer = []
for l in List:
    ans = 0
    for j in a:
        if l[j[1]-1] - l[j[0]-1] == j[2]:
            ans += j[3]
    answer.append(ans)
    
print(max(answer))

Submission status: Accepted

Solution code:
from collections import deque
N, M, Q = [int(a) for a in input().split()]
q = [None] * Q
for i in range(Q):
    q[i] = [int(x) for x in input().split()]

stk = deque([[i] for i in range(1, M + 1)])
ans = 0
while len(stk) > 0:
    A = stk.pop()
    if len(A) == N:
        temp = 0
        for i in range(Q):
            if A[q[i][1] - 1] - A[q[i][0] - 1] == q[i][2]:
                temp += q[i][3]
        ans = max(ans, temp)
        continue
    for i in range(A[-1], M + 1):
        stk.append(A + [i])

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
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())

pmax = 0
A = [i for i in range(1, m + 1)]
for L in combinations_with_replacement(A, n):
    l = sorted(list(L))
    p = 0
    for i in range(q):
        if l[b[i] - 1] - l[a[i] - 1] == c[i]:
            p += d[i]
    pmax = max(pmax, p)
print(pmax)