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(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)]
import itertools

A = []
M = []
for i in range(1, m+1):
    M.append(i)
for team in itertools.combinations_with_replacement(M, n):
    A.append(team)
    
B = [0]*len(A)
for i in range(q):
    a = abcd[i][0]
    b = abcd[i][1]
    c = abcd[i][2]
    d = abcd[i][3]
    for j in range(len(A)):
        if A[j][b-1] - A[j][a-1] == c:
            B[j] += d

print(max(B))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    res = []
    for e in range(1, 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):
                            for k in range(j, m + 1):
                                for l in range(k, m + 1):
                                    for o in range(l, m + 1):
                                        for p in range(o, m + 1):
                                            res.append([e, f, g, h, i, j, k, l, o, p])

    ans = 0
    for p in res:
        score = 0
        for a, b, c, d in ABCD:
            if p[b - 1] - p[a - 1] == c:
                score += d

        ans = max(ans, score)

    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

A = list(itertools.combinations_with_replacement(range(1,M+1), N))
number = len(A)

amount = 0
max_amount = 0
for i in range(number): #A
    
    for j in range(Q): # P
        bi = P[j][1]
        ai = P[j][0]
        if(A[i][bi-1] - A[i][ai-1] == P[j][2]):
            amount += P[j][3]
        
   # print(amount)
    
   # print(amount)
    if(amount >= max_amount):
        max_amount = amount
    
    amount = 0
    
print(max_amount)

Submission status: Accepted

Solution code:
import itertools

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

l = (list(itertools.combinations_with_replacement(range(1, M + 1), N)))
r = 0
result = 0
for k in l:
    r = 0
    for x in X:
        if k[x[1] - 1] - k[x[0] - 1] == x[2]:
            r += x[3]
    if result < r:
        result = r
print(result)

Submission status: Accepted

Solution code:
#c
import itertools

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

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

# n=3
# m=4
# q=3
# ls1 = [1, 3, 3, 100]
# ls2 = [1, 2, 2, 10]
# ls3 = [1, 1, 0, 1000]
# lslist = [ls1, ls2, ls3]

acomn = list(itertools.combinations_with_replacement(list(range(m)), n))

def tensu(ls, a):
    if a[ls[1]-1] - a[ls[0]-1] == ls[2]:
        return ls[3]
    else:
        return 0

def tensu2(lslist, a):
    return sum(list(map(lambda x: tensu(x, a), lslist)))

print(max(list(map(lambda a: tensu2(lslist, a), acomn))))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)  # import sysすること！再帰の深さ制限を緩くする
n, m, q = list(map(int, input().split()))
data = []
for i in range(q):
    a, b, c, d = list(map(int, input().split()))
    data.append([a-1, b-1, c, d])


def dfs(t):
    if len(t) == n:
        score = 0
        for a, b, c, d in data:
            if t[b] - t[a] == c:
                score += d
        global ans
        ans = max(ans, score)
        return

    if len(t) == 0:
        s = 1
    else:
        s = t[-1]

    for j in range(s, m+1):
        dfs(t+[j])


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

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as comb

n,m,q = map(int, input().split(' '))
lis = [list(map(int, input().split())) for _ in range(q)]
tes = comb(range(1,m+1),n)
res = 0
for i in tes:
    te = 0
    for a,b,c,d in lis:
        if c == i[b-1] - i[a-1]:
            te += d
    res = max(te,res)
print(res)

Submission status: Accepted

Solution code:
import itertools
n,m,q = map(int,input().split())
ab = [0]*q
for i in range(q):
    ab[i] = list(map(int,input().split()))
data = list(range(1,m+1))
ans = 0
a = list(itertools.combinations_with_replacement(data, n))
for s in a:
    score = 0
    for i in range(q):
        if s[ab[i][1]-1] != s[ab[i][0]-1] + ab[i][2]:
            pass
        else:
            score += ab[i][3]
    ans = max(ans,score)
print(ans)

Submission status: Accepted

Solution code:
import itertools
 
N,M,Q=map(int,input().split())
all=[]
 
for i in range(Q):
  all.append(list(map(int,input().split())))
#print(all)
#print(len(all))
#print(all[0][1])
 
x=sorted([i for i in range(1,M+1)])
maxdsum=0
 
 
for A in itertools.combinations_with_replacement(x, N):
  dsum=0
  #print("A=="+str(A))
  for num in range(Q):
    if A[all[num][1]-1]-A[all[num][0]-1]==all[num][2]:
      dsum+=all[num][3]
  if maxdsum<dsum:
    maxdsum=dsum
print(maxdsum)

Submission status: Accepted

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

al=list()

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


Sum=0
Summax=0
cnt=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): 
                                        cnt+=1
                                        Al=[i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]
                                        Sum=0
                                        for i in range(Q): 
                                            if(Al[al[i][1]-1]-Al[al[i][0]-1]==al[i][2]):
                                                Sum+=al[i][3]
                                        if(Summax<Sum):
                                            Summax=Sum

print(Summax)    
#print(cnt)

Submission status: Accepted

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

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

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

s = list(range(1, M + 1))
ans = 0


for s in combinations_with_replacement(s, N):
    num = 0
    for q in range(Q):
        a, b, c, d = abcd[q]
        if s[b - 1] - s[a - 1] == c:
            num += d
    ans = max(ans, num)

print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    res = 0
    for pattern in itertools.combinations_with_replacement(range(1, m + 1), n):
        score = 0
        for a, b, c, d in ABCD:
            if pattern[b - 1] - pattern[a - 1] == c:
                score += d
        res = max(res, score)

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement


n,m,q = map(int,input().split())
num_lst = []
for i in range(q):
    num_lst.append(list(map(int,input().split())))
l = list(range(1,m+1))
A = list(combinations_with_replacement(l,n))

mx = 0
for now_A in A:
    score = 0
    for nums in num_lst:
        a,b,c,d = nums
        if now_A[b-1] - now_A[a-1] == c:
            score += d
    mx = max(mx,score)
print(mx)

Submission status: Accepted

Solution code:
import itertools

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

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

score = 0
for _t in t:
    _s = 0
    for a, b, c, d in tmp:
        if c == _t[b - 1] - _t[a - 1]:
            _s += d
    score = max(_s, score)
print(score)

Submission status: Accepted

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

ans = 0
for i in itertools.combinations_with_replacement(range(1, m + 1), n):
    sub = 0
    for j in range(q):
        if i[ab[j][1] - 1] - i[ab[j][0] - 1] == ab[j][2]:
            sub += ab[j][3]
    
    ans = max(sub, ans)

print(ans)

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
check = list()
for i in range(Q):
  check.append(list(map(int, input().split())))
ans = 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):
                  L = [1, i1, i2, i3, i4, i5, i6, i7, i8, i9]
                  A = list()
                  for i in range(N):
                    A.append(L[i])
                  tmp = 0
                  for i in range(Q):
                    a = check[i][0]
                    b = check[i][1]
                    c = check[i][2]
                    d = check[i][3]
                    if(A[b-1]-A[a-1] == c):
                      tmp += d
                  ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
import math
import itertools

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


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

ls=list(con)

ans =[0]*len(ls)
k=0

for i in ls:
  for j in range(Q):
    if(i[ b[j]-1 ] - i[ a[j]-1 ]   == c[j] ):
      ans[k] += d[j]
  k += 1

print(max(ans))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase

def main():
    n,m,q=map(int,input().split())
    # print(n,m,q)
    a = [ [int(x) for x in input().split()] for _ in range(q) ]
    # print(a)
    ans=0

    def solve(b):
        
        if len(b)-1==n:
            cnt=0
            for v in a:
                if b[v[1]]-b[v[0]]==v[2]:
                    cnt+=v[3]
            nonlocal ans
            ans=max(ans,cnt) 
            return

        for i in range(b[-1],m+1):
            b.append(i)
            solve(b)
            b.pop()

    b=[1]
    solve(b)
    print(ans)

# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

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

lst = []
for i in range(Q):
    tmp = list(map(int, input().split()))
    lst.append(tmp)

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

max_num = 0

for s in seq:
    cnt = 0
    for l in lst:
        if s[l[1]-1] - s[l[0]-1] == l[2]:
            cnt += l[3]

    if max_num < cnt:
        max_num = cnt

print (max_num)

Submission status: Accepted

Solution code:
import itertools

n, m, q = map(int, input().split())
abcd = []
ans = 0

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

for comb in list(itertools.combinations_with_replacement(range(1, m + 1),n)):
    sum = 0
    for i in range(q):
        if comb[abcd[i][1] - 1] - comb[abcd[i][0] - 1] == abcd[i][2]:
            sum += abcd[i][3]
    if ans < sum:
        ans = sum

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

for i  in range(q):
    a[i],b[i],c[i],d[i]= map(int,input().split())
    
A=list(itertools.combinations_with_replacement([i for i in range(1,m+1)],n))


g=[]
for v in A:
    e=0
    for i in range(q):
        
        if v[b[i]-1]-v[a[i]-1] ==c[i]:
            e += d[i]
            
        
    g += [e]
print(max(g))

Submission status: Accepted

Solution code:
import math
import sys
import itertools

n,m,q=map(int,input().split())
a=[0]*q
b=[0]*q
c=[0]*q
d=[0]*q
e=[0]*m
for i in range(q): 
  a[i],b[i],c[i],d[i]=map(int,input().split())
for j in range(m):
  e[j]=j+1
total=0
maxnum=0
num=1<<len(e)
for current in itertools.combinations_with_replacement(e, n):
  if(len(current)==n):
    total=0
    #print(current)
    for i in range(q):
      if current[b[i]-1]-current[a[i]-1]==c[i]:
        total+=d[i]
    #print(total)
    maxnum=max(maxnum,total)
print(maxnum)

Submission status: Accepted

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

Submission status: Accepted

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

ans = 0
import itertools
for i in itertools.combinations_with_replacement(range(1, m+1), n):
    sumd = 0
    for j in abcd:
        if i[j[1]-1] - i[j[0]-1] == j[2]:
            sumd += j[3]
    ans = max(ans, sumd)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

for v in com:
    
    tot = 0
    for u in a:
        if v[u[1] - 1] - v[u[0] - 1] == u[2]:
            tot += u[3]
    if tot > max_:
        max_ = tot
        
print(max_)

Submission status: Accepted

Solution code:
import itertools

N, M, Q = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(Q)]
n = [i+1 for i in range(M)]
A_list = list(itertools.combinations_with_replacement(n,N))
ans = 0
for A in A_list:
    ans_ = 0
    for a, b, c, d in l:
        if A[b-1] - A[a-1] == c:
            ans_ += d
        ans = max(ans, ans_)

print(ans)

Submission status: Accepted

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

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

ans = []

for v in combinations_with_replacement(l, N):
  count = 0
  for i in range(Q):
    a, b, c, d = lists[i]
    if v[b-1] - v[a-1] == c:
      count += d
    ans.append(count)
print(max(ans))

Submission status: Accepted

Solution code:
import itertools
n,m,q=(int(i) for i in input().split())
l=[]
r=[i+1 for i in range(m)]
point=0
def checker(x,l):
  p=0
  for i in range(len(l)):
    if x[l[i][1]]-x[l[i][0]]==l[i][2]:
      p+=l[i][3]
  return p
for i in range(q):
  a,b,c,d=(int(i) for i in input().split())
  a-=1
  b-=1
  l.append([a,b,c,d])
for i in itertools.combinations_with_replacement(r,n):
  p=checker(i,l)
  if p>point:
    point=p
print(point)

Submission status: Accepted

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

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

import itertools

ans=0
for x in itertools.combinations_with_replacement(range(1,M+1),N):
    ans_temp=0
    for a,b,c,d in A:
        if x[b]-x[a]==c:
            ans_temp+=d
    ans=max(ans,ans_temp)

print(ans)

Submission status: Accepted

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

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

def check(t):
    ret=0
    for q in ql:
        if t[q[1]-1]-t[q[0]-1]==q[2]:
            ret+=q[3]

    return ret

print(max(map(check,itertools.combinations_with_replacement(range(1,m+1),n))))

Submission status: Accepted

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

ans = 0
for case in combinations([i for i in range(1,n+m)],n):
    now = 0
    A = [x-i for i,x in enumerate(case)]
    for i in range(q):
        a,b,c,d = abcd[i]
        if A[b-1]-A[a-1] == c:
            now += d
    ans = max(now,ans)

print(ans)

Submission status: Accepted

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

ans = 0
for A in itertools.combinations_with_replacement(range(1, M+1), N):
    A = sorted(list(A))
    point = 0
    for abcd in abcd_list:
        if A[abcd[1]-1] - A[abcd[0]-1] == abcd[2]:
            point += abcd[3]
    if point > ans:
        ans = point

print(ans)

Submission status: Accepted

Solution code:
import sys
import copy
sys.setrecursionlimit(10**9)
N,M,Q = list(map(int,input().split()))
A = []
for n in range(Q):
    a,b,c,d = map(int,input().split())
    A.append((a-1,b-1,c,d))

def dfs(arr, cur):
    if cur == N-1:
        score = 0
        for aa in A:
            a,b,c,d = aa 
            if arr[b]-arr[a] == c:
                score+=d
        return score
    else:
        mx = 0
        for s in range(arr[cur], M+1):
            arr = copy.copy(arr)
            # それ以降を1ふやす．
            for i in range(cur+1, N):
                arr[i] = s
            mx = max(mx, dfs(arr, cur+1))
        return mx


t = dfs([1 for i in range(N)], 0)
print(t)

Submission status: Accepted

Solution code:
import itertools

n, m, q = map(int, input().split())
value = []
for _ in range(q):
    a, b, c, d = map(int, input().split())
    value.append([a - 1, b - 1, c, d])
ans = 0
for comb in itertools.combinations_with_replacement(range(1, m + 1), n):
    temp = 0
    for v in value:
        if comb[v[1]] == comb[v[0]] + v[2]:
            temp += v[3]
    ans = max(ans, temp)
print(ans)

Submission status: Accepted

Solution code:
n,m,s=map(int,input().split())
a=[]
q=[[0]]
while q:
  x=q.pop()
  if len(x)<=n:
    if x[-1]==0:
      for j in range(1,m+1):
        c=x+[j]
        q.append(c)
    else:
      for j in range(x[-1],m+1):
        c=x+[j]
        q.append(c)
  else:
    a.append(x)
li=[tuple(map(int,input().split())) for _ in  range(s)]

ans=0
for A in a:
  s=0
  for i,j,k,l in li:
    if A[j]-A[i]==k:
      s+=l
  ans=max(ans,s)
print(ans)

Submission status: Accepted

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

from itertools import permutations,  combinations, accumulate, product, combinations_with_replacement
from functools import *
from collections import deque, defaultdict, Counter
from heapq import heapify, heappop, heappush, heappushpop


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

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

a_candidate = list(combinations_with_replacement(range(1, M + 1), N))

max_total = 0
for A in a_candidate:
    total = 0
    for abcd in abcd_ls:
        a, b, c, d = abcd
        a -= 1
        b -= 1
        if c == A[b] - A[a]:
            total += d
    max_total = max(total, max_total)

print(max_total)

Submission status: Accepted

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


for i in combinations_with_replacement(range(1,M+1), N):
    X = list(i)
    
    ans_1 = 0
    for k in S:
      if X[k[1]-1] - X[k[0]-1] == k[2]:
        ans_1 += k[3]
    if ans_1 > ans:
        ans = ans_1
      
print(ans)

Submission status: Accepted

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

def check(abcd, pattern):
    result = 0
    for a,b,c,d in abcd:
        if (pattern[b-1] - pattern[a-1]) == c:
            result += d
    return result

def main():
    N, M, Q = map(int, input().split())
    abcd = [list(map(int, input().split())) for _ in range(Q)]
    ans = 0
    for pattern in combinations_with_replacement(range(1, M+1), N):
        ans = max(ans, check(abcd, pattern))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

from itertools import combinations_with_replacement as CwR



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

Tables = list(CwR(range(1,m+1),n))
Sum_cor = []
for Table in Tables:
    d_sum = 0
    for l in Lis:
        if Table[l[1]-1]-Table[l[0]-1] == l[2]:
            d_sum+=l[3]
    Sum_cor.append(d_sum)

print(max(Sum_cor))

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
 
N, M, Q = map(int, input().split())
A = []
for i in range(Q):
    A.append(list(map(int, input().split())))
 
retsu = combinations_with_replacement(range(M), N)
result = 0
 
for i in retsu:
    score = 0
    for a in A:
        if i[a[1] - 1] - i[a[0] - 1] == a[2]:
            score += a[3]
    if result < score:
        result = score
 
print(result)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement, accumulate

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

ans = 0
for adds in combinations_with_replacement(range(n + 1), m - 1):
    arr = [0] * (n + 1)
    for i in adds:
        arr[i] += 1
    arr = list(accumulate(arr))
    score = 0
    for a, b, c, d in queries:
        if arr[b] - arr[a] == c:
            score += d
    ans = max(ans, score)

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as comb
n, m, q = map(int, input().split())
query = []
for _ in range(q):
    a, b, c, d = map(int, input().split())
    query.append((a-1, b-1, c, d))
ans = 0
for p in comb(list(range(1, m+1)), n):
    res = 0
    for a, b, c, d in query:
        if p[b]-p[a]==c:
            res+=d
    ans = max(ans, res)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N, M, Q = map(int, input().split())
ABCD = [list(map(int, input().split())) for _ in range(Q)]
ans = 0
q = deque()
q.append([1])
while q:
  A = q.pop()
  if len(A) == N+1:
    ans = max(ans, sum([d if A[b]-A[a] == c else 0 for a, b, c, d in ABCD]))
  else:
    for i in range(A[-1], M+1):
      q.append(A+[i])
print(ans)

Submission status: Accepted

Solution code:
import itertools
N, M, Q = map(int,input().split())
ABCD = [tuple(map(int, input().split())) for _ in range(Q)]
ans = 0
for s in itertools.combinations_with_replacement(range(1,M+1),N):
    temp = 0
    for i in range(Q):
        if s[ABCD[i][1]-1] - s[ABCD[i][0]-1] == ABCD[i][2]:
            temp += ABCD[i][3]
    ans = max(ans,temp)
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

[N, M, Q] = [int(x) for x in input().rstrip().split()]
A = []
B = []
C = []
D = []
score_dict = {}
for i in range(Q):
    [a, b, c, d] = [int(x) for x in input().rstrip().split()]
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)


def check_Q(temp_arr):
    tot_val = 0
    for i in range(Q):
        a = A[i]-1
        b = B[i]-1
        c = C[i]
        d = D[i]
        if temp_arr[b] - temp_arr[a] == c:
            tot_val += d

    return tot_val

temp_arr = [1 for _ in range(N)]
max_val = 0
while(True):
    #check_Q(temp_arr)
    temp_val = check_Q(temp_arr)
    #print(temp_arr, temp_val)
    if temp_val>max_val:
        max_val=temp_val

    for i in range(N):
        temp_arr[N-1-i]+=1
        if temp_arr[N-1-i] == M+1:
            temp_arr[N-1-i] = 0
            continue
        else:
            break

    if temp_arr[0] ==  0:
        break

    min_val=0
    for i in range(1,N):
        if temp_arr[i]<temp_arr[i-1]:
            temp_arr[i] = temp_arr[i-1]
    

print(max_val)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.buffer.readline

from itertools import combinations_with_replacement

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

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

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

ans = 0
for kumi in kumiawase:
    A = [0] + list(kumi)
    temp = 0
    for abcd in ABCD:
        a, b, c, d = abcd
        if A[b] - A[a] == c:
            temp += d
    ans = max(ans, temp)

print(ans)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import itertools
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))
N, M, Q = LI()

abcd = []

all = 0
for i in range(Q):
    a, b, c, d = LI()
    a -= 1
    b -= 1
    abcd.append([a, b, c, d])
    all += d

abcd = sorted(abcd, key= lambda x:x[3], reverse= True)
ans = 0
if Q <= 2:
    for q in range(Q):
        ans += abcd[q][-1]
    print(ans)
    sys.exit()

def cal_ans(A):
    ans = 0
    for i in range(Q):
        a, b, c, d = abcd[i]
        if A[b] - A[a] == c:
            ans += d
    return ans

def n2kdigit(n, k):
    bi=''
    before = 1
    while n!=0:
        if before <= (n % k):
            # print(n)
            bi+=str(n%abs(k))
            before = n % k
            if k<0:n=-(-n//k)
            else:n=n//k
        else:
            return None
    if len(bi) < N:
        return None
    return bi
ans = 0

for i in itertools.combinations_with_replacement(range(1, M+1), N):
    # print(i)
    ans = max(ans, cal_ans(i))
print(ans)

Submission status: Accepted

Solution code:
#!python3

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


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


def solve(A):
    n = len(A) - 1
    if n == N:
        return point(A)
    m = A[n]
    ans = 0
    for i in range(m, M + 1):
        ans = max(ans, solve(A + [i]))
    return ans


def main():
    ans = solve([1])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import itertools
def LI():return list(map(int,input().split()))

n,m,q=LI()
abcd=[]
for _ in range(q):
    a,b,c,d=LI()
    a-=1
    b-=1
    abcd.append((a,b,c,d))

# 数列Aの生成
Alist=itertools.combinations_with_replacement(range(m),n)
ans=0
for A in Alist:
    cnt=0
    for a,b,c,d in abcd:
        if A[b]-A[a]==c:
            cnt+=d
    ans=max(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
# Aは長さn,1以上m以下の単調増加整数列

import itertools

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

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

As = itertools.combinations_with_replacement(range(m), n)


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


print(max([calc(A) for A in As]))

Submission status: Accepted

Solution code:
import itertools

N, M, Q = map(int, input().split())
a = [0] * Q
b = [0] * Q
c = [0] * Q
d = [0] * Q

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

maxx = 0
for p in itertools.combinations_with_replacement(range(M), N):
    sum = 0
    for j in range(Q):
        if p[b[j] - 1] - p[a[j] - 1] == c[j]:
            sum += d[j]
    maxx = max(sum, maxx)
print(maxx)