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
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
inf = 10**17
mod = 10**9 + 7
#s=input().rstrip()

n,m,q=MI()
strs=[[[] for i in range(m)] for i in range(n)]
for i in range(m):
    strs[0][i].append(str(i))
#print(strs)
for i in range(n-1):
    for j in range(m):
        for k in range(j,m):
            for s in strs[i][k]:
                strs[i+1][j].append(str(j)+s)
#print(strs)

L=strs[n-1]
#print(L)
lis=[]
for i in range(m):
    for s in L[i]:
        lis.append(s)
#print(lis)
mx=0
zyou=[LI() for i in range(q)]
for u in lis:
    po=0
    for k in range(q):
        a,b,c,d=zyou[k]
        if int(u[b-1])-int(u[a-1])==c:
            po+=d
    if po>mx:
        mx=po
print(mx)

Submission status: Accepted

Solution code:
# import copy
N, M, Q = [eval(v) for v in input().strip().split(" ")]

a_list, b_list, c_list, d_list = [], [], [], []

for k in range(Q):
    a, b, c, d = [eval(v) for v in input().strip().split(" ")]
    a_list.append(a)
    b_list.append(b)
    c_list.append(c)
    d_list.append(d)

max_value = 0

def calc_score(complete_A):
    score = 0
    for i in range(Q):
        if complete_A[b_list[i]] - complete_A[a_list[i]] == c_list[i]:
            score += d_list[i]
    return score

def search(A, M, depth, a_list, b_list, c_list, d_list, max_value, count):
    # print("%s: %s" % (depth, A))
    # count += 1
    # if count > 20:
    #     exit(0)
    if depth > 0:
        last_A = A[-1]
        for k in range(last_A, M + 1):
            # next_A = copy.deepcopy(A)
            # next_A.append(k)
            next_A = A + [k]
            max_value = search(next_A, M, depth - 1, a_list, b_list, c_list, d_list, max_value, count)
    else:
        value = calc_score(A[1:])
        if value > max_value:
            max_value = value
    return max_value

count = 0
A = [1]
print(search(A, M, N + 1, a_list, b_list, c_list, d_list, max_value, count))

Submission status: Accepted

Solution code:
import sys
from itertools import combinations_with_replacement as cwr
input = sys.stdin.readline

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
combs = list(cwr(range(1,M+1),N))
ans = [0]*(len(combs))
for i,comb in enumerate(combs):
    for a,b,c,d in zip(A,B,C,D):
        if comb[b-1] - comb[a-1] ==c:
            ans[i] += d
print(max(ans))

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

ps = list(combinations_with_replacement(range(1, m+1), n-1))
n_p = len(ps)

for i in range(n_p):
    ns = [1] + list(ps[i])
    ss = 0
    for j in range(q):
        k = l[j]
        if ns[k[1]-1] - ns[k[0]-1] == k[2]:
            ss += k[3]
    s.append(ss)

print(max(s))

Submission status: Accepted

Solution code:
from itertools import*
n,m,q,*L=map(int,open(0).read().split())
print(max(sum(d*(x[b-1]-x[a-1]==c)for a,b,c,d in zip(*[iter(L)]*4))for x in combinations_with_replacement(range(m),n)))

Submission status: Accepted

Solution code:
import itertools

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

a, b, c, d = [0] * Q, [0] * Q, [0] * Q, [0] * Q
for i in range(Q):
    a[i], b[i], c[i], d[i] = map(int, input().split())

M_list = [_ for _ in range(1, M+1)]
A_list = []
for pair in itertools.combinations_with_replacement(M_list, N):
    A_list.append(pair)

sum_list = []
for i in range(len(A_list)):
    sum_list_ = []
    for j in range(Q):
        if A_list[i][b[j]-1] - A_list[i][a[j]-1] == c[j]:
            sum_list_.append(d[j])
    sum_list.append(sum(sum_list_))

print(max(sum_list))

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n, m, q = map(int, input().split())
dict_list = {}
key_list = []
for i in range(0, q):
    a, b, c, d =  map(int, input().split())
    key = tuple([a, b, c])
    key_list.append(key)
    dict_list[key] = d

def func(i, k, a_list):
    if k == 0:
        temp_score = 0 
        for key in key_list:
            if key[2] == a_list[key[1]-1] - a_list[key[0]-1]:
                temp_score += dict_list[key]
        return temp_score
    k = k - 1
    max_score = 0
    for j in range(i, m + 1):
        max_score = max(func(j, k, a_list + [j]), max_score)
    return max_score
score = 0
for i in range(1, m + 1):
    score = max(func(i, n - 1, [i]), score)
print(score)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
from itertools import combinations

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

D = defaultdict(dict)
for a, b, c, d in ABCD:
  D[b-1][(a-1, c)] = d

for j in range(N-1, 0, -1):
  for x, y in combinations(D[j], 2):
    if x[0] == y[0]:
      continue
    if x[0] > y[0]:
      x, y = y, x
    if x[1] > y[1]:
      if (x[0], x[1] - y[1]) not in D[y[0]]:
        D[y[0]][(x[0], x[1] - y[1])] = 0

for j in range(1, N):
  if (j-1, 0) not in D[j]:
    D[j][(j-1, 0)] = 0

que = deque([([1], 0)])
memo = set([(1,)])
ans = 0
while que:
  L, score = que.popleft()
  if len(L) == N:
    if score > ans:
      ans = score
  else:
    for a, c in D[len(L)]:
      l = L[a] + c
      if L[-1] <= l <= M:
        x = tuple(L + [l])
        if x not in memo:
          memo.add(x)
          que.append((L + [l], score + sum(d for v, d in D[len(L)].items() if l - L[v[0]] == v[1])))
print(ans)

Submission status: Accepted

Solution code:
import math
import itertools

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

ans_list=list()
ans=0
xans=0

lis =  list(range(1,m+1))
for team in itertools.combinations_with_replacement(lis,n):
  
    for i in range(q):
      
      lix=li[i].split()
      
      if team[int(lix[1])-1]-team[int(lix[0])-1]==int(lix[2]):
        ans=int(lix[3])
        xans+=ans
        
       
        
    ans_list+=[xans]
    xans=0
      
    
    
print(max(ans_list))

Submission status: Accepted

Solution code:
import itertools

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

seleted = [x for x in range(1, m+1)]
A_list = list(itertools.combinations_with_replacement(seleted, n))
for A in A_list:
    tmp = 0
    for q in q_list:
        if A[q[1]-1] - A[q[0]-1] == q[2]:
            tmp += q[3]
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
def count_up(x,n):
  x[n]+=1
  if x[n]>m:
    count_up(x,n-1)
    x[n]=x[n-1]
  return
n,m,q=map(int,input().split())
abcd=[map(int,input().split()) for _ in range(q)]
a,b,c,d=[list(i) for i in zip(*abcd)]
x=[1,1,1,1,1,1,1,1,1,1,1]
ans=0
if m==1:
  temp=0
  for i in range(q):
    if x[b[i]]-x[a[i]]==c[i]:
      temp+=d[i]
  ans=max(ans,temp)
else:
  while x[1]==1:
    temp=0
    for i in range(q):
      if x[b[i]]-x[a[i]]==c[i]:
       temp+=d[i]
    ans=max(ans,temp)
    count_up(x,n)
print(ans)

Submission status: Accepted

Solution code:
import itertools

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


hoge = []
kouho = list(range(1,M+1))
for i in itertools.combinations_with_replacement(kouho, N):
    hoge.append(i)

Anss = []*len(hoge)
m = 0
for i in range(0,len(hoge)):
  for j in range(0,Q):
    if(hoge[i][l[j][1]-1] - hoge[i][l[j][0]-1] == l[j][2]):
      m = m + l[j][3]
  Anss.append(m)
  m = 0
  
  
ans = max(Anss)
print(ans)

Submission status: Accepted

Solution code:
import itertools as itr
N,M,Q = map(int,input().split())
sheat = list()
for i in range(Q):
    sheat.append(list(map(int,input().split())))

comb = tuple(itr.combinations_with_replacement(range(1,M+1),N))
Maxsum = 0
# print(sheat)
# print(comb)
sumd = 0
for i in range(len(comb)):
    ansum = 0
    for j in range(Q):
        if(comb[i][sheat[j][1]-1]-comb[i][sheat[j][0]-1] == sheat[j][2]):
            ansum += sheat[j][3]
           
    if(Maxsum < ansum):
        Maxsum = ansum
    # print(ansum)
print(Maxsum)      
# for i in range(Q):
#     sumd += sheat[i][3]
# print(sumd)
#nCm

#A_1,A_2,A_3,...A_n,M
#A_b-i - A_a-i = C_i  :Sum di

# A= {1,3,4} :comb          ↓sheat
#  i = 1:4 - 1 = 3o 100     [1,3,3]
#      2:3 - 1 = 2o  10     [1,2,2]
#      3:4 - 3 = 1*  10     [2,3,2]
#                   110

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
a = []
for i in range(Q):
	a.append(list(map(int, input().split())))
P = 0
for i in range(1,M+1):
	for p in range(i,M+1):
		for j in range(p,M+1):
			for k in range(j,M+1):
				for m in range(k,M+1):
					for n in range(m,M+1):
						for o in range(n,M+1):
							for q in range(o,M+1):
								for r in range(q,M+1):
									for s in range(r,M+1):
										l=[i,p,j,k,m,n,o,q,r,s]
										ans=0
										for b in range(Q):
											if l[a[b][1]-1]-l[a[b][0]-1]==a[b][2]:
												ans+=a[b][3]
										P=max(P,ans)
print(P)

Submission status: Accepted

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

def dfs( s , n ):
    i = 0
    if len(s) >= n:
        ans.append(s)
        return
    else:
        a = int(s[len(s)-1])
        for j in range(m-a):
            dfs( s + str(a+j) , n )
                
ans = []
for j in range(m):
    ak = str(j)
    dfs( ak , n )
    
tans = 0
for i in range(len(ans)):
    an = 0
    s = [0]*(n+1)
    for j in range(n):
        s[j+1] = int(ans[i][j])
    for j in range(q):
        if s[b[j]] - s[a[j]] == c[j]:
            an += d[j]
                  
    tans = max(tans,an)
    
print(tans)

Submission status: Accepted

Solution code:
import itertools
from collections import deque


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

    m = list(range(1, M + 1))
    As = []
    A = [0 for _ in range(N)]
    for i in m:
        # i = 2
        A[0] = i
        sub_m = m[i - 1:]
        for j in sub_m:
            # j = 3
            A[1] = j
            sub_m = m[j - 1:]

            if N == 2:
                As.append(A)
                A = A.copy()
                continue

            for k in sub_m:
                # k=3
                A[2] = k
                sub_m = m[k - 1:]

                if N == 3:
                    As.append(A)
                    A = A.copy()
                    continue

                for n in sub_m:
                    # k=3
                    A[3] = n
                    sub_m = m[n - 1:]

                    if N == 4:
                        As.append(A)
                        A = A.copy()
                        continue

                    for o in sub_m:
                        # k=3
                        A[4] = o
                        sub_m = m[o - 1:]

                        if N == 5:
                            As.append(A)
                            A = A.copy()
                            continue

                        for p in sub_m:
                            # k=3
                            A[5] = p
                            sub_m = m[p - 1:]

                            if N == 6:
                                As.append(A)
                                A = A.copy()
                                continue

                            for q in sub_m:
                                # k=3
                                A[6] = q
                                sub_m = m[q - 1:]

                                if N == 7:
                                    As.append(A)
                                    A = A.copy()
                                    continue

                                for r in sub_m:
                                    # k=3
                                    A[7] = r
                                    sub_m = m[r - 1:]

                                    if N == 8:
                                        As.append(A)
                                        A = A.copy()
                                        continue

                                    for s in sub_m:
                                        # k=3
                                        A[8] = s
                                        sub_m = m[s - 1:]

                                        if N == 9:
                                            As.append(A)
                                            A = A.copy()
                                            continue

                                        for t in sub_m:
                                            # k=3
                                            A[9] = t
                                            sub_m = m[t - 1:]

                                            As.append(A)
                                            A = A.copy()

    ans = 0
    for A in As:
        # i=0; A = As[i]
        score = 0
        for i, l in enumerate(ls):
            # i=0; l=ls[i]
            if A[l[1] - 1] - A[l[0] - 1] == l[2]:
                score += l[3]
        if score >= ans:
            ans = score

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy

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)

seq = [[] for i in range(n)]

for i in range(1, m + 1):
  seq[0].append([i])

for i in range(1, n):
  for j in range(len(seq[i - 1])):
    s = copy.copy(seq[i - 1][j])
    s.append(0)
    for k in range(s[-2], m + 1):
      s[-1] = k
      s2 = copy.copy(s)
      seq[i].append(s2)

score = [0 for i in range(len(seq[n - 1]))]
for i in range(len(seq[n - 1])):
  for j in range(q):
    if seq[n - 1][i][b[j] - 1] - seq[n - 1][i][a[j] - 1] == c[j]:
      score[i] += d[j]

print(max(score))

Submission status: Accepted

Solution code:
n, m, q = input().split()
n = int( n )
m = int( m )
q = int( q )
a = []
b = []
c = []
d = []
for i in range( int( q ) ):
    a_i, b_i, c_i, d_i = input().split()
    a.append( int( a_i ) )
    b.append( int( b_i ) )
    c.append( int( c_i ) )
    d.append( int( d_i ) )

array = [ 1 ] * n
array_list = [ array ]

i = 0
while True:
    for k in range( array_list[i][-1], m + 1 ):
        array_list.append( array_list[i][1:] + [ k ] )
        #print( array_list[i][1:] + [ k ] )
    i = i + 1
    if len( array_list ) > 100000:
        break

max_score = 0
for array in array_list:
    score = 0
    for i in range( q ):
        #print( i, a[i], b[i], c[i], array )
        if array[b[i]-1] - array[a[i]-1] == c[i]:
            score = score + d[i]
    if max_score < score:
        max_score = score

print( max_score )

Submission status: Accepted

Solution code:
import itertools as it
 
n,m,q = map(int, input().split())
l = [list(map(int, input().split())) for i in range(q)]
ans = 0
 
for v in list(it.combinations_with_replacement(range(1,m+1),n)):
    num = 0
    for w in l:
        x,y,z = w[0]-1,w[1]-1,w[2]
        if v[y] - v[x] == z:
            num += w[3]
    if num > ans:
        ans = num
print(ans)

Submission status: Accepted

Solution code:
def rec(L):
    return sum([d for a, b, c, d in X if L[b] - L[a] == c]) if len(L) > N else max([rec(L + [i]) for i in range(L[-1], M)])

N, M, Q = map(int, input().split())
X = []
for _ in range(Q):
    a, b, c, d = map(int, input().split())
    X.append((a, b, c, d))
print(rec([0]))

Submission status: Accepted

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

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

A_score = 0
for A in A_possible:
    A_sum = 0
    for i in range(Q):
        A_test = A[a_b_c_d[i][1]-1] - A[a_b_c_d[i][0]-1]
        if A_test == a_b_c_d[i][2]:
            A_sum += a_b_c_d[i][3]
    if A_score < A_sum:
        A_score = A_sum
print(A_score)

Submission status: Accepted

Solution code:
import itertools

def main():
    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())

    seq = [i for i in range(1, min(11, M+1))]

    max_point = 0

    for e in list(itertools.combinations_with_replacement(seq, N)):
        point = 0
        for i in range(Q):
            if e[b[i]-1] - e[a[i]-1] == c[i]:
                point += d[i]
        if point >= max_point:
            max_point = point

    print(max_point)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
n,m,q = map(int,input().split())
group = []
for i in range(q):
  w,x,y,z = map(int,input().split())
  v = (w,x,y,z)
  group.append(v)
#groupに(a,b,c,d)がタプルで入っている
max_value = max(group[i][3] for i in range(len(group)))

#Aの配列を試す

l = [i for i in range(1,m+1)]
h = itertools.combinations_with_replacement(l,n)
array =[]

for v in h:
    array.append(v)
#arrayが全ての配列になった


for j in range(len(array)):
  total = 0
  for i in range(q):
    if array[j][group[i][1]-1] - array[j][group[i][0]-1] == group[i][2]:
      total += group[i][3]
  if total >= max_value:
    max_value = total  

print(max_value)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
import sys
input = sys.stdin.readline
N,M,Q=(int(x) for x in input().rstrip('\n').split())
ress=[x for x in combinations_with_replacement(range(1,M+1),N)]
res_dict = {}
for i in range(Q):
  res_dict[i] = [int(x) for x in input().rstrip('\n').split()]
res_s = []
for i in ress:
  match=0
  for x in range(Q):
    if i[res_dict[x][1]-1]-i[res_dict[x][0]-1]==res_dict[x][2]:
      match += res_dict[x][3]
  res_s.append(match)
print(max(res_s))

Submission status: Accepted

Solution code:
import itertools

n, m, q = map(int, input().split(' '))
a = [list(map(int, input().split(' '))) for i in range(q)]
b = list(itertools.combinations_with_replacement(range(1, m+1), n))
c = 0
d = 0
for i in range(len(b)):
	for j in range(len(a)):
		if b[i][(a[j][1]-1)] - b[i][(a[j][0]-1)] == a[j][2]:
			c += a[j][3]
	if d <= c:
		d = c
	c = 0
print(d)

Submission status: Accepted

Solution code:
from itertools import *

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

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

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

a=list(combinations_with_replacement(aaa,n))
ans=0
for i in a:
    aa=0
    for j in l:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            aa+=j[3]
    if aa>ans:
        ans=aa
print(ans)

Submission status: Accepted

Solution code:
rd = dict()
rd[0] = 0
def check(x):
    r = 0
    for a, b, c, d in X:
        if x[b-1]-x[a-1] == c:
            r += d
    return r

def dfs(x, l):
    if len(x) == N:
        rd[0] = max(rd[0], check(x))
        return
    for i in range(l, M+1):
        dfs(x+[i], i)
N, M, Q = map(int, input().split())
X = []
for _ in range(Q):
    a, b, c, d = map(int, input().split())
    X.append((a, b, c, d))
dfs([], 1)
print(rd[0])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

def iter_A(N,M_,M):
    if N==1:
        yield from ([a] for a in range(M_,M+1))
    else:
        for a in range(M_,M+1):
            yield from ([a] + b for b in iter_A(N-1,a,M))

def solve():
    N, M, Q = map(int, input().split())
    E = {}
    X = []
    for q in range(Q):
        a,b,c,d = map(int, input().split())
        X.append((a-1,b-1,c,d))

    
    return str(max(sum(d for a,b,c,d in X if A[b]-A[a]==c) for A in iter_A(N,1,M)))


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

Submission status: Accepted

Solution code:
s = list(map(int, input().split()))
n = s[0]
m = s[1]
q = s[2]

abcd = []

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

maximum = 0

for i1 in range(1, m + 1):
    for i2 in range(i1, m + 1):
        for i3 in range(i2, m + 1):
            for i4 in range(i3, m + 1):
                for i5 in range(i4, m + 1):
                    for i6 in range(i5, m + 1):
                        for i7 in range(i6, m + 1):
                            for i8 in range(i7, m + 1):
                                for i9 in range(i8, m + 1):
                                    for i10 in range(i9, m + 1):
                                        iarray = [i1, i2, i3, i4, i5, i6, i7, i8, i9, i10]
                                        goukei = 0
                                        for j in range(q):
                                            if iarray[abcd[j][1] - 1] - iarray[abcd[j][0] - 1] == abcd[j][2]:
                                                goukei = goukei + abcd[j][3]

                                        if goukei > maximum:
                                            maximum = goukei

print(maximum)

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-

def solve():
    import copy

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

    cands = []
    def rec(start, lst):
        if len(lst) == N:
            return lst

        for i in range(start, M+1):
            tmp_lst = copy.deepcopy(lst)
            tmp_lst.append(i)
            ret = rec(i, tmp_lst)
            if ret is not None:
                cands.append(ret)

    rec(1, [])

    ans = 0
    for cand in cands:
        total = 0
        for abcd in query:
            a,b,c,d = abcd
            if cand[b-1]-cand[a-1] == c:
                total += d
        ans = max(ans, total)

    print(ans)




if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import itertools
N, M, Q = map(int, input().split())
query = [list(map(int, input().split())) for _ in range(Q)]
l = list(range(1, M+1))
ans = 0
for v in itertools.combinations_with_replacement(l, N):
    A = sorted(list(v))
    cost = 0
    for i in range(Q):
        if A[query[i][1]-1] - A[query[i][0]-1] == query[i][2]:
            cost += query[i][3]
    ans = max(ans, cost)
print(ans)

Submission status: Accepted

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

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

s = [1] * (n)

ans = []

def dfs(k, c,old,ans):
    #ans = 0
    #print(s,k)
    if k == n:
        tmp = 0
        for i in range(q):
            if s[abcd[i][1]-1] - s[abcd[i][0]-1] == abcd[i][2]:
                tmp += abcd[i][3]
        #ans = max(ans,tmp)
        ans.append(tmp)
        return# ans
    for i in range(old,c+1):
        #print(old,c+1)
        s[k] = i
        dfs(k+1, m,i,ans)
        #print(k+1,c)
    #s[k] = chr(c+ord('a'))
    #dfs(k+1, c+1)
    return ans

print(max(dfs(0, m,1,ans)))

Submission status: Accepted

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

ANS = []

if n == 2:
    for a in range(1,m+1):
        for b in range(a,m+1):
            ANS.append([a,b])
            
if n == 3:
    for a in range(1,m+1):
        for b in range(a,m+1):
            for c in range(b,m+1):
                ANS.append([a,b,c])
                
if n == 4:
    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):
                    ANS.append([a,b,c,d])
                    
if n == 5:
    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):
                        ANS.append([a,b,c,d,e])
                        
if n == 6:
    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):
                            ANS.append([a,b,c,d,e,f])
                        
if n == 7:
    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):
                                ANS.append([a,b,c,d,e,f,g])
                                
if n == 8:
    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):
                                    ANS.append([a,b,c,d,e,f,g,h])
                                    
if n == 9:
    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):
                                        ANS.append([a,b,c,d,e,f,g,h,i])
                                        
if n == 10:
    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):
                                            ANS.append([a,b,c,d,e,f,g,h,i,j])
                                            
ans = 0

for i in ANS:
    point = 0
    for j in ABCD:
        a = j[0] - 1
        b = j[1] - 1
        c = j[2]
        d = j[3]
        
        if i[b] - i[a] == c:
            point += d
            
    ans = max(ans,point)
    
print(ans)

Submission status: Accepted

Solution code:
def read_int():
    return int(input())

def read_int_map():
    return map(int,input().split(' '))

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

def read_s_list_loop(n):
    return [input() for _ in range(n)]

N,M,Q = read_int_map()
ans_map = {}

abcd_list = []
for i in range(Q):
    abcd_list.append(read_int_list())

abcd_list.sort(key=lambda x:(x[0],x[1]))

for abcd in abcd_list:
    a,b,c,d = map(int,abcd)

import copy
import sys
sys.setrecursionlimit(36288000)
all_list = []
def make_list(current=1,n=10,m=10,current_list=[],cnt=0):
    cnt += 1
    for i in range(current,m):
        tmp = copy.deepcopy(current_list)
        tmp.append(i)
        if cnt == n:
            global all_list
            all_list.append(tmp)
        else:
            make_list(i,n,m,tmp,cnt)
make_list(current=1,n=N,m=M+1,current_list=[],cnt=0)
ans = 0
for An in all_list:
    tmp = 0
    for abcd in abcd_list:
        a,b,c,d = map(int,abcd)
        if An[b-1] - An[a-1] == c:
            tmp += d
    ans = max(tmp,ans)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""
def main():
    N, M, Q = map(int, input().split())
    r_list = []
    for i in range(Q):
        r_list.append(list(map(int, input().split())))
    max_score = 0
    a1 = 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):
                                        a_list = [a1,a2,a3,a4,a5,a6,a7,a8,a9,a10]
                                        score = 0
                                        for r in r_list:
                                            if a_list[r[1]-1] - a_list[r[0]-1] == r[2]:
                                                score += r[3]
                                        max_score = max(score, max_score)
    print(max_score)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools
N,M,Q = map(int, input().split())
l = [[int(i) for i in input().split()] for j in range(Q)]
A = []
nums = list(range(1,M+1))
for B in itertools.combinations_with_replacement(nums, N):
	A.append(B)

A_s = []*len(A)
m = 0
for i in range(0,len(A)):
  for j in range(0,Q):
    if(A[i][l[j][1]-1] - A[i][l[j][0]-1] == l[j][2]):
      m = m + l[j][3]
  A_s.append(m)
  m = 0
ans = max(A_s)
print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M,Q= list(map(int, input().split(' ')))
L=[]
for i in range(Q):
    L.append(list(map(int, input().split(' '))))
A=[i + 1 for i in range(M)]
As=list(itertools.combinations_with_replacement(A, N))
S=[]
s=0
for I in As:
    for J in L:
        if I[J[1]-1]-I[J[0]-1]==J[2]:
                s=s+J[3]
    S.append(s)
    s=0
print(max(S))