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:
n, m, q = map(int, input().split())   
a = []
for i in range(10):
  a.append(1)
max = 0
inp = []
for i in range(q):
  ta,tb,tc,td = map(int,input().split())
  inp.append((ta,tb,tc,td))
for i1 in range(1,m+1):
  a[0] = i1
  for i2 in range(i1,m+1):
    a[1] = i2
    for i3 in range(i2,m+1):
      a[2] = i3
      for i4 in range(i3,m+1):
        a[3] = i4
        for i5 in range(i4,m+1):
          a[4] = i5
          for i6 in range(i5,m+1):
            a[5] = i6
            for i7 in range(i6,m+1):
              a[6] = i7
              for i8 in range(i7,m+1):
                a[7] = i8
                for i9 in range(i8,m+1):
                  a[8] = i9
                  for i10 in range(i9,m+1):
                    a[9] = i10
                    sum = 0
                    if q != 1:
                      for i in range(q):
                        if a[inp[i][1]-1] - a[inp[i][0]-1] == inp[i][2]:
                          sum = sum + inp[i][3]
                        if sum > max:
                          max = sum
                    else:
                      if a[inp[0][1]-1] - a[inp[0][0]-1] == inp[0][2]:
                          sum = sum + inp[0][3]
                      if sum > max:
                          max = sum

print(max)

Submission status: Accepted

Solution code:
N,M,Q = map(int,input().split())
# 10個の数列で、A_i <= A_i+1となる組み合わせ（最大10）は
# [1,1,1,1,1,1,1,1,1,1]のどこに10個のUPを入れるかの組み合わせであり
# 20C10 = 184756
# この組み合わせに対して最大50のクエリを試すと、9237800通り
# 全探索する

query = [None] * Q
for i in range(Q):
  query[i] = list(map(int,input().split()))
  
stack = []
for i in range(1,M + 1):
  stack.append([i])

def calc(arr,query):
  res = 0
  for q in query:
    a,b,c,d = q
    if arr[b-1] - arr[a-1] == c:
      res += d
  return res
  
ans = 0
while stack:
  arr = stack.pop()
  if len(arr) == N:
    val = calc(arr,query)
    if val > ans:
      ans = val
    continue
  for i in range(arr[-1],M+1):
    stack.append(arr + [i])

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
import copy

N,M,Q=map(int, sys.stdin.readline().split())
X=[ map(int, sys.stdin.readline().split()) for _ in range(Q) ]

qq=deque()
for m in range(1,M+1):
    q=deque()
    q.append([m])
    while q:
        if N<len(q[0]):
            qq+=q
            break
        fro=q.popleft()
        if N<len(fro):break
        last=fro[-1]
        for to in range(last,M+1):
            q.append(fro+[to])

ans=float("-inf")
for L in qq:
    temp_ans=0
    for a,b,c,d in X:
        if L[b-1]-L[a-1]==c:
            temp_ans+=d
    ans=max(ans,temp_ans)
print ans

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

N, M, Q, *ABCD = map(int, open(0).read().split())

L = list(zip(*[iter(ABCD)] * 4))

print(max(sum(d for a, b, c, d in L if A[b - 1] - A[a - 1] == c) for A in combinations_with_replacement(range(1, M + 1), N)))

Submission status: Accepted

Solution code:
import itertools

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

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

ans = 0
for A in As:
    sm = 0
    for abcd in abcds:
        a, b, c, d = abcd[0], abcd[1], abcd[2], abcd[3]
        if A[b-1] - A[a-1] == c:
            sm += d
    ans = max(ans, sm)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, M, Q = mi()
abcd = li2(Q)

'''
a = '0' * N
m = str(M-1)
l = [a]

while True:
    i = N-1
    while i >= 0 and a[i] == m:
        i -= 1
    if i == -1:
        break
    a = list(a)
    num = str(int(a[i]) + 1)
    a[i] = num
    if i != N-1:
        for j in range(i+1, N):
            a[j] = num
    tmp = ''.join(a)
    l.append(tmp)
'''

def dfs(num, length):
    if length == N:
        l.append(num)
        return
    last = int(num[-1])
    for i in range(last, M):
        dfs(num + str(i), length+1)

l = []
dfs('0', 1)

ans = 0
for num in l:
    cnt = 0
    num = list(map(int, list(num)))
    for i in range(Q):
        if num[abcd[i][1]-1] - num[abcd[i][0]-1] == abcd[i][2]:
            cnt += abcd[i][3]
    ans = max(ans, cnt)

print(ans)

Submission status: Accepted

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

def calc(p):
    ret = 0
    # 各条件を満たしていれば、dを加算していく
    for a, b, c, d in abcd:
        if p[b-1] - p[a-1] == c:
            ret += d
    return ret

ans = [0]
def dfs(s):
    if len(s) == N:
        ans[0] = max(ans[0], calc(s))
        return
    for i in range(s[-1],M+1):
        dfs(s+[i])

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

print(ans[0])

Submission status: Accepted

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

for i in range(q):
    arr[i][0],arr[i][1],arr[i][2],arr[i][3]=map(int, input().split())

ans=0
for i in itertools.combinations_with_replacement(range(1,m+1),n):
    score=0
    for j in range(q):
        tmp1=i[arr[j][1]-1]
        tmp0=i[arr[j][0]-1]
        if tmp1-tmp0==arr[j][2]:
            score+=arr[j][3]
    if ans<score:
        ans=score
print(ans)

Submission status: Accepted

Solution code:
## coding: UTF-8


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

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

def add(l):
    ret = []
    for i in range(len(l)):
        last = l[i][-1]
        for j in range(last, M+1):
            ret.append(l[i] + [j])
    return ret

for i in range(N-1):
    dfs = add(dfs)
#print(dfs)


m = -1
for i in range(len(dfs)):
    A = dfs[i]
    tmp = 0
    for j in range(len(lq)):
        aj = lq[j][0]
        bj = lq[j][1]
        cj = lq[j][2]
        dj = lq[j][3]
        #print('i:{}, j:{}, A:{}, [aj, bj, cj, dj]:{}'.format(i, j, A, lq[j]))
        #print('A[bj-1]:{}, A[aj-1]:{}, A[bj-1]-A[aj-1]:{}, cj:{}, ==?:{}, dj:{}'.format(A[bj-1], A[aj-1], A[bj-1]-A[aj-1], cj,   A[bj-1]-A[aj-1]==cj  , dj))
        #print('i:{}, j:{}, A:{}, lq[j]:{}'.format(i, j, A, lq[j]))
        #print('A[lq[j][i]-1]:{}, A[lq[j][0] - 1]:{}'.format(A[lq[j][i]-1], A[lq[j][0] - 1]))
        #if(A[lq[j][i]-1] - A[lq[j][0] - 1] == lq[2]):
            #tmp += lq[3]
        if(A[bj-1]-A[aj-1] == cj):
            tmp += dj
    #print('i:{}, A:{}, tmp:{}'.format(i, A, tmp))
    if(tmp > m):
        m = tmp    
print(m)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
from itertools import combinations_with_replacement
if __name__ == "__main__":
    N, M, Q = map(int, input().split())
    #data = np.array([list(map(int, input().split())) for _ in range(Q)])
    data = [list(map(int, input().split())) for _ in range(Q)]
    #print(data)
    # A = data[:, 0]
    # B = data[:, 1]
    # C = data[:, 2]
    # D = data[:, 3]
    #print("B {}".format(len(B.shape)))

    # 1, 2, ..., M から重複を許してN個取り出す（ソート済み）
    arr = combinations_with_replacement(range(1, M+1), N)
    ans = 0
    for a in arr:
        #print(a)
        s = 0
        # for i in range(Q):
        #     if a[data[i, 1]-1] - a[data[i, 0]-1] == data[i, 2]:
        #         s += data[i, 3]
        for d in data:
            if a[d[1]-1] - a[d[0]-1] == d[2]:
                s += d[3] 

        if s > ans:
            ans = s
    print(ans)

Submission status: Accepted

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

a=[]
for i in range(n-1):
  a.append(1)
a.append(0)
current=0
b=[]
for i in range(n):
  b.append(m)

while True:
  i=n-1
  while a[i]==m:
    i=i-1
    if i==-1:
      break
  if i==-1:
    break
  a[i]+=1
  for j in range(i+1,n):
      a[j]=a[i]
  d=0
  for j in range(q):
    if (a[l[j][1]-1]-a[l[j][0]-1])==l[j][2]:
      d+=l[j][3]
  if d>current:
    current=d

print(current)

Submission status: Accepted

Solution code:
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())
A = [1] * 10
 
def check(A, ans):
  t = 0
  for i in range(q):
    if A[b[i]-1] - A[a[i]-1] == c[i]:
      t += d[i]
  if ans < t: return t
  else: return ans
 
ans = 0
for i1 in range(1, m+1):
  A[1] = i1
  for i2 in range(i1, m+1):
    A[2] = i2
    for i3 in range(i2, m+1):
      A[3] = i3
      for i4 in range(i3, m+1):
        A[4] = i4
        for i5 in range(i4, m+1):
          A[5] = i5
          for i6 in range(i5, m+1):
            A[6] = i6
            for i7 in range(i6, m+1):
              A[7] = i7
              for i8 in range(i7, m+1):
                A[8] = i8
                for i9 in range(i8, m+1):
                  A[9] = i9
                  ans = check(A, ans)
print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m,q=map(int,input().split())
l=[list(map(int,input().split())) for i in range(q)]
M=[i+1 for i in range(m)]
L=[]
for i in itertools.combinations_with_replacement(M,n):
  L.append(i)
ans=[]
for i in range(len(L)):
  ct=0
  for j in range(q):
    if L[i][l[j][1]-1]-L[i][l[j][0]-1]==l[j][2]:
      ct+=l[j][3]
  ans.append(ct)
print(max(ans))

Submission status: Accepted

Solution code:
import itertools

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

x = []

for _ in range(q):
    x.append(list(map(int,input().split())))

res = 0

for l in itertools.combinations_with_replacement([x for x in range(m)], n):
    temp = 0
    
    for temp_x in x:
        if l[temp_x[1] - 1] - l[temp_x[0] - 1] == temp_x[2]:
            temp += temp_x[3]

    if res <= temp:
        res = temp

print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


from itertools import combinations_with_replacement
n, m, q = inpl()
ans=0
data=[inpl() for _ in range(q)]
for t in combinations_with_replacement(range(1,m+1), n):
    tmp = 0
    for a,b,c,d in data:
        if t[b - 1] - t[a - 1] == c:
            tmp += d
    ans = max(tmp, ans)
print(ans)

Submission status: Accepted

Solution code:
N,M,Q = map(int,input().split())
abcd = [list(map(int,input().split())) for _ in range(Q)]
ans = 0
def res(lis,place,now_number,M,N,result):
  if place==N-1:
    lis[place]=now_number
    result.append(lis.copy())
    return
  else:
    lis[place]=now_number
    for j in range(now_number,M+1):
      res(lis,place+1,j,M,N,result)

for i in range(1,M+1):
  result = []
  place = 0
  l = [0]*N
  res(l,place,i,M,N,result)
  for A in result:
    tmp = 0
    for q in abcd:
      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:
import itertools

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

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

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

Max_amount = 0
for v in itertools.combinations_with_replacement(l, N):
    L = list(v)
    amount = 0
    for i in range(Q):
        if L[B[i]-1] - L[A[i]-1] == C[i]:
            amount += D[i]
    if Max_amount < amount:
        Max_amount = amount

print(Max_amount)

Submission status: Accepted

Solution code:
import itertools
n, m, q = map(int, input().split())
Q = []
for i in range(q):
    ai, bi, ci, di = map(int, input().split())
    Q.append([ai,bi,ci,di])

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

ans = -1
for x in X:

    p = 0
    for q in Q:
        if x[q[1]-1] - x[q[0]-1] == q[2]:
            p += q[3]

    if ans < p:
        ans = p


print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as combr

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

ans = 0
# lis = list(range(1, M+1))
for pair in combr(range(1,M+1), N):
    tmp = 0
    pair = list(pair)
    for i in range(Q):
        if (pair[b[i]-1]-pair[a[i]-1]) == c[i]:
            tmp += d[i]
            
    ans=max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N, M, Q = map(int, input().split())
ABCD = [list(map(int, input().split())) for _ in range(Q)]

# V[k] : 長さkである単調増加数列たち
V = [[] for _ in range(N+1)]

# 初期値として長さ1のものを入れる
for i in range(1, M+1):
    V[1].append([i])

# V[k] から V[k+1] を作る
for i in range(1, N):
    for v in V[i]:
        # 単調増加なので、末尾の値以上であるものを全て試す
        b = v[-1]
        for a in range(b, M+1):
            v2 = v + [a]
            V[i+1].append(v2)

ans = 0
for v in V[N]:
    res = 0
    for a, b, c, d in ABCD:
        if v[b-1] - v[a-1] == c:
            res += d
    ans = max(ans, res)

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

ans = 0

for i in combinations_with_replacement(range(1, m + 1), n):
    s = 0
    for a, b, c, d in qx:
        s += d if (i[b-1] - i[a-1] == c) else 0
    ans = max(ans, s)

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as cwr

N, M, Q, *Z = map(int, open(0).read().split())
*Z, = zip(*[iter(Z)]*4)

ans = 0
for A in cwr(range(M), N):
    score = 0
    for a, b, c, d in Z:
        if A[b-1]-A[a-1] == c:
            score += d

    if score > ans:
        ans = score

print(ans)

Submission status: Accepted

Solution code:
n, m, q = map(int, input().split())
a = [0]*q
b = [0]*q
c = [0]*q
d = [0]*q
for i in range(q):
  a[i], b[i], c[i], d[i] = map(int, input().split())
A = [1] * 10
 
def check(A, ans):
  t = 0
  for i in range(q):
    if A[b[i]-1] - A[a[i]-1] == c[i]:
      t += d[i]
  if ans < t:
    return t
  else:
    return ans
 
ans = 0
for i1 in range(1, m+1):
  A[1] = i1
  for i2 in range(i1, m+1):
    A[2] = i2
    for i3 in range(i2, m+1):
      A[3] = i3
      for i4 in range(i3, m+1):
        A[4] = i4
        for i5 in range(i4, m+1):
          A[5] = i5
          for i6 in range(i5, m+1):
            A[6] = i6
            for i7 in range(i6, m+1):
              A[7] = i7
              for i8 in range(i7, m+1):
                A[8] = i8
                for i9 in range(i8, m+1):
                  A[9] = i9
                  ans = check(A, ans)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
import copy

N,M,Q=map(int, sys.stdin.readline().split())
X=[ map(int, sys.stdin.readline().split()) for _ in range(Q) ]

qq=deque()
for m in range(1,M+1):
    q=deque()
    q.append([m])
    flag=True
    while flag:
        fro=q.popleft()
        if N<len(fro):break
        last=fro[-1]
        for to in range(last,M+1):
            if N<len(fro+[to]):
                q.append(fro)
                qq+=q
                flag=False
                break
            q.append(fro+[to])

ans=float("-inf")
for L in qq:
    temp_ans=0
    for a,b,c,d in X:
        if L[b-1]-L[a-1]==c:
            temp_ans+=d
    ans=max(ans,temp_ans)
print ans

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as cwd

n,m,q = map(int,input().split())
A = list(cwd(range(1,m+1),n))
l = []
ans = 0

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

for j in A:
    tmp = 0
    for k in l:
        if j[k[1]] - j[k[0]] == k[2]:
            tmp += k[3]
    ans = max(ans,tmp)

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n,m,q=l_in()

abcd=[l_in() for _ in range(q)]

s = []


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

def search(s, current):
    tmp = 0
    for d in range(current, m+1):
        s.append(d)
        if len(s) == n:
            tmp = max(tmp, check(s))
        else:
            tmp = max(tmp, search(s, d))
        s.pop()
        
    return tmp

print(search(s,1))

Submission status: Accepted

Solution code:
import itertools
n,m,q=map(int,input().split())
lis=[i for i  in range(1,m+1)]
lis=list(itertools.combinations_with_replacement(lis,n))
box=[0 for j in range(len(lis))]
for i in range(q):
    que=list(map(int,input().split()))
    for j in range(len(lis)):
        if lis[j][que[1]-1]-lis[j][que[0]-1]==que[2]:
            box[j]+=que[3] 
print(max(box))

Submission status: Accepted

Solution code:
import numpy as np
import itertools


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

vals = []
for i in range(Q):
    vals.append(list(map(int, input().split(" "))))
    
maxv = 0
cand = list(itertools.combinations_with_replacement(range(1, M+1), N))
for c in cand:
    sumv = 0
    for v in vals:
        if (c[v[1]-1] - c[v[0]-1]) == v[2]:
            sumv += v[3]
    if maxv < sumv:
        maxv = sumv
print(maxv)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**6)

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

def search(lis):
    global n,m,score
    if len(lis)==n:
        total = 0
        for s in score:
            if lis[s[1]-1]-lis[s[0]-1]==s[2]: total += s[3]
        return total
        
    first = 1 if len(lis) == 0 else lis[-1]
    res = []
    for i in range(first, m+1):
        nlis = lis + [i]
        res.append(search(nlis))
    return max(res)

print(search([]))

Submission status: Accepted

Solution code:
import itertools
n, m, q = map(int, input().split())
LIST = []
for i in range(q):
    t = list(map(int, input().split()))
    LIST.append(t)
# print(LIST)

l = []
for j in range(1, m+1):
    l.append(j)
ans = 0
for a in itertools.combinations_with_replacement(l, n):
    # print(a)
    # 得点を計算する
    score = 0
    for i in range(q):
        if a[LIST[i][1]-1]-a[LIST[i][0]-1] == LIST[i][2]:
            score += LIST[i][3]
    ans = max(score, ans)
print(ans)

Submission status: Accepted

Solution code:
n,m,q = map(int,input().split())
u = []
for i in range(q):
    u.append(list(map(int,input().split())))
"""
a = [i[0] for i in u]
b = [i[1] for i in u]
c = [i[2] for i in u]
d = [i[3] for i in u]
"""
z = []
import itertools
a = itertools.combinations_with_replacement([i for i in range(1,m+1)],n)
for e in a:
    sum = 0
    for i in range(q):
        if e[u[i][1]-1]-e[u[i][0]-1] == u[i][2]:
            sum += u[i][3]
    z.append(sum)

print(max(z))

Submission status: Accepted

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

def check(A, ans):
  t = 0
  for i in range(q):
    if A[b[i]-1] - A[a[i]-1] == c[i]:
      t += d[i]
  if ans < t:
    return t
  else:
    return ans

ans = 0
for i1 in range(1, m+1):
  A[1] = i1
  if n >= 3:
    for i2 in range(i1, m+1):
      A[2] = i2
      if n >= 4:
        for i3 in range(i2, m+1):
          A[3] = i3
          if n >= 5:
            for i4 in range(i3, m+1):
              A[4] = i4
              if n >= 6:
                for i5 in range(i4, m+1):
                  A[5] = i5
                  if n >= 7:
                    for i6 in range(i5, m+1):
                      A[6] = i6
                      if n >= 8:
                        for i7 in range(i6, m+1):
                          A[7] = i7
                          if n >= 9:
                            for i8 in range(i7, m+1):
                              A[8] = i8
                              if n >= 10:
                                for i9 in range(i8, m+1):
                                  A[9] = i9
                                  ans = check(A, ans)
                              else:
                                ans = check(A, ans)
                          else:
                            ans = check(A, ans)
                      else:
                        ans = check(A, ans)
                  else:
                    ans = check(A, ans)
              else:
                ans = check(A, ans)
          else:
            ans = check(A, ans)
      else:
        ans = check(A, ans)
  else:
    ans = check(A, ans)
print(ans)

Submission status: Accepted

Solution code:
import copy
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])    
B=[]
def dfs(A,l):
    if l==n:
        B.append(A)
    else:
        for i in range(A[-1],m+1):
            nA=copy.copy(A)
            nA.append(i)
            dfs(nA,l+1)
dfs([1],1)

ans=0
for ls in B:
    cnt=0
    for que in Q:
        if ls[que[1]]-ls[que[0]]==que[2]:
            cnt+=que[3]
    ans=max(cnt,ans)
print(ans)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs,itertools
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

N,M,Q = m()

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

data = []

ma = 0

for i in range(Q):
    data.append(l())
    
for i in dp:
    po = i
    te = 0
    for j in range(len(data)):
        a,b,c,d = data[j]
        if po[b-1]-po[a-1] == c:
            te += d
    ma = max(ma,te)
print(ma)

Submission status: Accepted

Solution code:
import itertools
def main():
    N, M, Q = map(int, input().split())
    query = [[int(a) for a in input().split()] for i in range(Q)]
    st = ""
    for i in range(M):
        st += str(i)

    total = 0
    for comb in itertools.combinations_with_replacement(st, N):
        A = [ int(a)+1 for a in comb]
        s = 0
        for a, b, c, d in query:
            if A[b-1] - A[a-1] == c:
                s += d
        
        if total < s:
            total = s

    print(total)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

def main():
  N, M, Q = map(int, input().split())
  abcd = [list(map(int, input().split())) for x in range(Q)]
  ans = 0
  for x in combinations_with_replacement(range(1, M+1), N):
    r = 0
    for a,b,c,d in abcd:
      if x[b-1] - x[a-1] == c:
        r += d
    ans = max(ans,r)
  print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

s_max = 0
for l in list(itertools.combinations_with_replacement(range(1, m+1), n)):
    score = 0
    for nums in nums_list:
        if l[nums[1]-1] - l[nums[0]-1] == nums[2]:
            score += nums[3]
    if score > s_max:
        s_max = score

print(s_max)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

def readlines(n):
  for _ in range(n):
    a,b,c,d = map(int,input().split())
    yield a,b,c,d
    
def main():
  N,M,Q = map(int, input().split())
  X = list(readlines(Q))
  
  for comb in combinations_with_replacement(range(1,M+1),N):

    x = 0
    for a,b,c,d in X:
      if comb[b-1] - comb[a-1] == c:
        x += d
    yield x

print(max(main()))

Submission status: Accepted

Solution code:
#20C10のcombinatrics全探索？
#本番でCでこれ見たら凍るw
#少なくとも combinatrics が組込みでなかったら C問題 じゃないな
n,m,q=map(int, input().split( ))
qs=tuple(tuple(map(int, input().split( ))) for _ in range(q))
import itertools
ans=0
for comb in itertools.combinations(range(1,n+m),n):##+1ない?
    tmp=0
    comb2=[comb[i]-i for i in range(n)]
    for ai,bi,ci,di in qs:
        if comb2[bi-1]-comb2[ai-1]==ci:
            tmp+=di 
    ans=max(ans,tmp)
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())
  
ans = 0      
def dfs(A):
  global ans
  if len(A) >= n:    
    tmp = 0
    for i in range(q):
      if A[b[i]-1] - A[a[i]-1] == c[i]:
        tmp += d[i]
    ans = max(ans,tmp)
  else:
    s = 1
    if len(A)>0:
      s = A[-1]    
    for i in range(s-1,m):
      dfs(A+[i+1])

A = []
dfs(A) 
print(ans)

Submission status: Accepted

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

n,m,q = map(int,input().split())
all_num = [i for i in range(1, m+1)]
M = []
ans = []
for _ in range(q):
    a,b,c,d = map(int,input().split())
    M.append([a,b,c,d])


ans = 0
for com in list(itertools.combinations_with_replacement(all_num, n)):
    score = 0
    for m in M:
        if com[m[1]-1]-com[m[0]-1] == m[2]:
            score += m[3]
    
    ans = max(ans,score)

print(ans)

Submission status: Accepted

Solution code:
import itertools

def main():
    n,m,q = tuple([int(t)for t in input().split()])

    a = [[int(t)for t in input().split()]for _ in [0]*q]
    
    ans = []
    for lst in itertools.combinations_with_replacement(range(1,m+1),n):
        t = 0
        for a_i,b_i,c_i,d_i in a:
            t +=  d_i if lst[b_i-1]-lst[a_i-1]==c_i else 0
        ans.append(t)
    
    print(max(ans))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
n,m,q=map(int,input().split())
abcd=[list(map(int,input().split())) for _ in range(q)]
seq=list(combinations_with_replacement(range(1,m+1),n))
ans=0
for s in seq:
    cand=0
    for a,b,c,d in abcd:
        a-=1
        b-=1
        if s[b]-s[a]==c:
            cand+=d
    ans=max(ans,cand)
print(ans)

Submission status: Accepted

Solution code:
import itertools

def main():
    n,m,q = map(int,input().split())
    a = [0] * (q+1)
    b = [0] * (q+1)
    c = [0] * (q+1)
    d = [0] * (q+1)

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

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

    ans = 0
    for A in Alist:
        cnt = 0
        for i in range(1,q+1):
            if A[b[i]-1] - A[a[i]-1] == c[i]:
                cnt += d[i]
        ans = max(ans,cnt)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#template
def inputlist(): return [int(k) for k in input().split()]
#template
N,M,Q = inputlist()
l = [0]*Q
for i in range(Q):
    l[i] = inputlist()
li = [int(i) for i in range(1,M+1)]
from itertools import combinations_with_replacement
h = combinations_with_replacement(li,N)
ans = 0
for v in h:
    va = list(v)
    tmp = 0
    for i in range(Q):
        a,b,c,d = l[i]
        a-=1
        b-=1
        if va[b] - va[a] == c:
            tmp += d
    ans = max(tmp,ans)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as combr

ii = lambda:int(input())
li = lambda:list(map(int,input().split()))

def main(n,m,q,l):
    res = 0
    for item in combr(range(1,m+1),n):
        res = max(res, calc(item, l))
    return res

def calc(item,l):
    res = 0
    for i in l:
        a,b,c,d = i[0],i[1],i[2],i[3]
        if item[b-1] - item[a-1] == c:
            res += d
    return res

n,m,q = li()
l = list(li() for _ in range(q))

print(main(n,m,q,l))

Submission status: Accepted

Solution code:
import itertools
 
N, M, Q = map(int, input().split())
cmb = [list(map(int, input().split())) for _ in range(Q)]
 
def score(seq):
  s = 0
  for q in range(Q):
    if seq[cmb[q][1]-1] - seq[cmb[q][0]-1] == cmb[q][2]:
      s += cmb[q][3]
  return s
 
p = [i for i in range(1, M+1)]
A = itertools.combinations_with_replacement(p, N)
ans = 0
for a in A:
  ans = max(ans, score(a))
print(ans)