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 itertools
n, m, q = map(int, input().split())
a = []
b = []
c = []
d = []
for i in range(q):
	aa, bb, cc, dd = map(int, input().split())
	a.append(aa)
	b.append(bb)
	c.append(cc)
	d.append(dd)
ary = [i+1 for i in range(m)]
ans = 0
for i in itertools.combinations_with_replacement(ary,n-1):
	x = list(i)
	x.append(1)
	x.sort()
	cnt = 0
	for j in range(q):
		if x[b[j]-1] - x[a[j]-1] == c[j]:
			cnt += d[j]
	ans = max(ans,cnt)
print (ans)

Submission status: Accepted

Solution code:
from functools import lru_cache

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

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

@lru_cache(maxsize=None)
def search(mi, A):
    if len(A) > N:
        return 0

    ret = 0
    for i in range(1, A[-1] + 1):
        ret = max(ret, search(i, A + (i,)))

    d = len(A)
    for b, c, d in BCD[N - d]:
        if A[-(b + 1)] - A[-1] == c:
            ret += d
    return ret

ans = 0
for i in range(1, M + 1):
    ans = max(ans, search(i, (i,)))
print(ans)

Submission status: Accepted

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

def dfs(pos,a,m,cs):
    if pos==len(a):
        s=0
        for i in cs:
            if a[i[1]-1]-a[i[0]-1]==i[2]:s+=i[3]
        return s

    ans=0
    if pos==0:low=1
    else:low=a[pos-1]
    for i in range(low,m+1):
        a[pos]=i
        ans=max(ans,dfs(pos+1,a,m,cs))  #pos+1 实现调用
    return ans





print(dfs(0,[0]*n,m,cs))

Submission status: Accepted

Solution code:
import sys
import itertools
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

# 1～Mまでの数を複数回用いて、長さNの要素の部分列返す
#（combinations：複数使用なし、combinations_with_replacement：複数使用あり）
A = np.array(list(itertools.combinations_with_replacement(range(1, M + 1), N)))

n = len(A) # 組合せ総数
score = np.zeros(n, np.int32) # [0,0,...,0] :0が n個のaraay

m = map(int, read().split())
for a, b, c, d in zip(m, m, m, m):
    cond = A[:, b - 1] - A[:, a - 1] == c
    score += d * cond

print(score.max())

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import itertools
N,M,Q=list(map(int,input().split()))
query=list()
for _ in range(Q):
    query.append(list(map(int,input().split())))

ans = 0
for an in itertools.combinations_with_replacement(range(1,M+1),N):
    score = 0
    for a,b,c,d in query:
        if an[b-1] - an[a-1] == c:
            score += d
    ans = max(ans,score)
print(ans)

Submission status: Accepted

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

B = [i for i in range(1, m+1)]
# 重複組み合わせ
A = combinations_with_replacement(B, n)
ans = []
for item in A:
    res = 0
    for i in range(q):
        if item[b[i]-1] - item[a[i]-1] == c[i]:
            res += d[i]
            ans.append(res)
print(max(ans))

Submission status: Accepted

Solution code:

N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]
for i in range(len(abcd)):
    abcd[i][0] -= 1
    abcd[i][1] -= 1
    
options = ["A","B"]   
all_patterns = options

for i in range(N+M-2):
    all_patterns = [i+j for j in options for i in all_patterns if str(i+j).count("A") <=N and str(i+j).count("B") <= M-1]

for i in range(len(all_patterns)):
    num = []
    count = 1
    for j in range(N+M-1):
        if all_patterns[i][j] == "A":
            num.append(count)
        else:
            count+=1
    all_patterns[i] = num

all_scores = [0 for _ in range(len(all_patterns))]
for i, char in enumerate(all_patterns):
    for a,b,c,d in abcd:
        if int(char[b]) - int(char[a]) == c:
            all_scores[i]+= d

print(max(all_scores))

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
Q=[list(map(int,input().split())) for i in range(q)]
ans=0
#めっちゃfor文あるならdfs
R=[range(i,m) for i in range(m)]
def dfs(d,s,l):
    global n,m,Q,ans
    if d==n:
        ans_=0
        for k in Q:
            a,b,c,e=k
            if int(s[b-1])-int(s[a-1])==c:
                ans_+=e
        ans=max(ans,ans_)
    else:
        for i in R[l]:
            dfs(d+1,s+str(i),i)
dfs(0,"",0)

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)

#global ans
ans = 0

def dfs(k, c,old):
    global ans
    #awr = 0
    #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)
        #print(k+1,c)
    #s[k] = chr(c+ord('a'))
    #dfs(k+1, c+1)
    #return ans

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

Submission status: Accepted

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

ans=0
for c in combinations_with_replacement(range(n),m-1):
    A=[0]*n
    for i in c:
        A[i]+=1
    for i in range(1,n):
        A[i]+=A[i-1]
    score=0
    #print(A,c)
    for a,b,c,d in Q:
        if A[b-1]-A[a-1]==c:
            score+=d
    ans=max(ans,score)
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
import collections
# X = int(input())
N, M, Q = map(int, input().split())
As =[0]
Bs =[0]
Cs =[0]
Ds =[0]
 
for i in range(Q):
	a, b, c, d = map(int, input().split())
	As.append(a)
	Bs.append(b)
	Cs.append(c)
	Ds.append(d)
 
lst = range(1, M+1)
AAss = list(itertools.combinations_with_replacement(lst, N))

rCs = collections.Counter()
# for i, c in enumerate(Cs):
	# print(i)
	# rCs[c] = Ds[i]
max_score = 0
# print("rCs")
# print(rCs)
for AAs in AAss:
	score = 0
	# print("AAs")
	# print(AAs)
	AAs = [0] + list(AAs)
	for i in range(1,Q+1):
		# print("AAs[Bs[i]] - AAs[As[i]]")
		# print(AAs[Bs[i]] - AAs[As[i]])
		if Cs[i] == AAs[Bs[i]] - AAs[As[i]]:
			score+=Ds[i]
		# print("dif_score")
 
	if score > max_score:
		max_score = score
	# print("score")
	# print(score)
print(max_score)

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[i] -= 1
    b[i] -= 1

ans = 0
for seq in itertools.combinations_with_replacement(range(1, M+1), N):
    tmp = 0
    for i in range(Q):
        if seq[b[i]] - seq[a[i]] == c[i]:
            tmp += d[i]
    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m,q = map(int,input().split())
ch = list(itertools.combinations_with_replacement(range(1,m+1),n))
lch = len(ch)
rel = [0]*lch
l = [list(map(int,input().split())) for _ in range(q)]
for k in range(lch):
    for i in range(q):
        if ch[k][l[i][1]-1]-ch[k][l[i][0]-1]==l[i][2]:
            rel[k]+=l[i][3]
print(max(rel))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from itertools import combinations_with_replacement
def main():
    n,m,q=map(int,input().split())
    lis=list(combinations_with_replacement(range(1,m+1),n))
    ans=0
    Q=[[int(_) for _ in input().split()] for i in range(q)]
    for l in lis:
        cunt=0
        for q in Q:
            if int(l[q[1]-1])-int(l[q[0]-1])==q[2]:
                cunt+=q[3]
        ans=max(ans,cunt)
    print(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)]

ans = 0
for pat in combinations_with_replacement(range(1, m + 1), n):
    sm = 0
    for a, b, c, d in abcd:
        a -= 1
        b -= 1
        if pat[b] - pat[a] == c:
            sm += d

    ans = max(ans, sm)

print(ans)

Submission status: Accepted

Solution code:
import time
startTimeProblem=time.time()

import fileinput, sys, itertools, functools
from math import *
from bisect import *
from heapq import *
from collections import *

def lcm(a, b):  
    return (a*b)/gcd(a, b)

class InputHelper:
    def __init__(self):
        self.myinput = fileinput.input()

    def isLocal(self):
        return not fileinput.isstdin()

    def int(self):
        return int(self.myinput.readline().rstrip())

    def ints(self):
        return [int(_) for _ in self.myinput.readline().rstrip().split()]

    def str(self):
        return self.myinput.readline().rstrip()

    def strs(self):
        return [_ for _ in self.myinput.readline().rstrip().split()]

class OutputHelper:
    def int(self, a):
        print(a)    

    def ints(self, a):  
        print(" ".join([str(_) for _ in a]))
    
    def intsNL(self, a):
        for _ in a:
            print(_)
    
    def str(self, s):
        print(s)

    def strs(self, s):
        print(" ".join([_ for _ in s]))

    def strsNL(self, s):
        for st in s:
            print(st)

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

In = InputHelper()
Out = OutputHelper()

######################################

N, M, Q = In.ints()


fromTo = defaultdict(list)

for i in range(Q):
    a, b, c, d = In.ints()

    fromTo[a].append((b,c,d))

ans = 0

def rec(arr,N,M,fromTo):
    if len(arr)==N:
        points = 0

        for i in range(len(arr)):
            idx = i+1
            if idx in fromTo:
                for rule in fromTo[idx]:
                    b,c,d = rule
                    if arr[b-1]-arr[i]==c:
                        points+=d
        global ans
        ans = max(ans, points)
        return

    highest = arr[-1]

    for i in range(highest, M+1):
        arr.append(i)
        rec(arr,N,M,fromTo)
        arr.pop(-1)


rec([1],N,M,fromTo)


Out.int(ans)

######################################

if len(sys.argv)>2 and sys.argv[2]=="TIMEIT":
    fin = (time.time()-startTimeProblem)*1000
    print("{:.2f}".format(fin) + "ms")

Submission status: Accepted

Solution code:
# coding: utf-8
import re
import math
from collections import defaultdict
import itertools
from copy import deepcopy
import random
from heapq import heappop,heappush
import time
import os
import queue
import sys
import datetime
from functools import lru_cache
#@lru_cache(maxsize=None)
readline=sys.stdin.readline
sys.setrecursionlimit(2000000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def is_power(a,b):#aはbの累乗数か
    now=b
    while now<a:
        now*=b
    if now==a:return True
    else:return False
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def get_facs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(a,b,c):
    if a:return b
    else:return  c
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n,type_="dict"):
    b = 2
    list_ = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            list_.append(b)
        b+=1
    if n > 1:list_.append(n)
    if type_=="dict":
        dic={}
        for a in list_:
            if a in dic:
                dic[a]+=1
            else:
                dic[a]=1
        return dic
    elif type_=="list":
        return list_
    else:
        return None
def floor_(n,x=1):
    return x*(n//x)
def ceil_(n,x=1):
    return x*((n+x-1)//x)
def hani(x,min_,max_):
    ret=x
    if x<min_:ret=min_
    if x>max_:ret=max_
    return ret
def seifu(x):
    return x//abs(x)
###################################################
X=[]
def f(arr,n,m):
    if len(arr)==n:
        X.append(arr[:])
    else:
        for a in range(arr[-1],m+1):
            aarr=arr[:]
            aarr.append(a)
            f(aarr,n,m)
def main():
    n,m,q=map(int,input().split())
    for a in range(1,m+1):f([a],n,m)
    A=[0]*q
    B=[0]*q
    C=[0]*q
    D=[0]*q
    ans=0
    for a in range(q):A[a],B[a],C[a],D[a]=map(int,input().split())

    for x in X:
        ssum=0
        for i in range(q):
            if x[B[i]-1]-x[A[i]-1]==C[i]:
                ssum+=D[i]
        ans=max(ans,ssum)
    print(ans)
main()

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
n, m, k = map(int, input().split())
arr = [x for x in range(1, m + 1)]
p = list(combinations_with_replacement(arr, n))
query = []
for i in range(k):
    a, b, c, d = map(int, input().split())
    pp = [a, b, c, d]
    query.append(pp)
m = []
summ = 0

for j in p:

    for k in query:
        a1, b1, c1, d1 = k[0]-1, k[1]-1, k[2], k[3]
        if j[b1] - j[a1] == c1:

            summ += d1

    m.append(summ)

    summ = 0
print(max(m))

Submission status: Accepted

Solution code:
import itertools
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

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

ans = 0
for A in itertools.combinations_with_replacement(range(1, M + 1), r=N):
    score = 0
    for a, b, c, d in abcd:
        if A[b - 1] - A[a - 1] == c:
            score += d
    if ans < score:
        ans = score
print(ans)

Submission status: Accepted

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

ans = 0
for A in itertools.combinations_with_replacement(range(1, M+1), N):
    tmp = sum([x[3] for x in X if A[x[1]-1] - A[x[0]-1] == x[2]])
    if tmp > ans:
        ans = tmp
print(ans)

Submission status: Accepted

Solution code:
N,M,Q = map(int,input().rstrip().split(" "))
i = 0
K = []

A = [1] * N
A.append(M)
E = [M] * (N + 1)

q = []

karians = 0
ans = 0
for _ in range(Q):
    q.append(list(map(int,input().split(" "))))

while True:
    karians = 0
    for qq in q:
        if A[qq[1] -1] - A[qq[0] -1] == qq[2]:
            karians += qq[3]
    if karians > ans:
        ans = karians
    if A == E:
        break
    i = 0
    A[0] += 1
    while A[i] == A[i + 1] + 1:
        A[i] = 1
        A[i + 1] += 1
        i += 1
        if i == N - 1:
            break
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import combinations_with_replacement
 
n, m, q = map(int, input().split())
 
pt = np.array(list(combinations_with_replacement(range(1,m+1), n)))
score = np.zeros(len(pt))
 
for i in range(q):
    a, b, c, d =map(int, input().split())
    flg = pt[:,b-1] - pt[:,a-1] == c
    score += flg * d
#    print(score)
 
print(int(score.max()))

Submission status: Accepted

Solution code:

ANS = 0

n, m, q = (int(i) for i in input().split())
t = []
for i in range(q):
	t.append([int(i) for i in input().split()])

def sml(lst):
	# ~ print("lst=",lst)
	ret = 0
	for x in t:
		# ~ print("x = ",x)
		if lst[x[1]-1] - lst[x[0]-1] == x[2]:
			ret+= x[3]
	return ret

def f(k, n, m, lst):
	if k==n:
		ans = sml(lst)
		# ~ print(lst,"->", ans)
		global ANS
		ANS = max(ans, ANS)
	elif k==0:
		for i in range(1,m+1):
			lst+=[i]
			f(k+1, n, m, lst)
			lst.pop()
	else:
		for i in range(lst[-1], m+1):
			lst+=[i]
			f(k+1, n, m, lst)
			lst.pop()
			
f(0,n,m,[])
	
print(ANS)

Submission status: Accepted

Solution code:
from copy import deepcopy

# 入力
N, M, Q = map(int, input().split())
a, b, c, d = [], [], [], []
for _ in range(Q):
    a_, b_, c_, d_ = map(int, input().split())
    a.append(a_ - 1)
    b.append(b_ - 1)
    c.append(c_)
    d.append(d_)

# 変数定義
max_sum_d = 0

def judgeA(A):
    global max_sum_d
    sum_d = 0
    for a_, b_, c_, d_ in zip(a, b, c, d):
        if A[b_] - A[a_] == c_:
            sum_d += d_
    max_sum_d = max(sum_d, max_sum_d)

# 関数定義
def dfsA(A, left):
    for i in range(left, M + 1):
        A_ = deepcopy(A)
        A_.append(i)
        if len(A_) == N:
            judgeA(A_)
        else:
            dfsA(A_, i)

# 実行
dfsA([], 1)
print(max_sum_d)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement, combinations

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

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

l = {(a-1, b-1, c): d for a, b, c, d in abcd}

r = 0
for poses in combinations_with_replacement(range(m), n):
    s = 0
    for pos in combinations(enumerate(poses), 2):
        k = (pos[0][0], pos[1][0], pos[1][1]-pos[0][1])
        if k in l:
            s = s + l[k]
    if s > r:
        r = s

print(r)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
n, m, q = map(int, input().split())
abcd = [tuple(map(int, input().split()))for _ in range(q)]
ans = 0
for x in combinations_with_replacement(range(1, m+1), n):
    cnt = 0
    for a, b, c, d in abcd:
        if x[b-1]-x[a-1] == c:
            cnt += d
    if ans < cnt:
        ans = cnt

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import combinations_with_replacement


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


def slv(N, M, Q, ABCD):
    ans = 0
    for a in combinations_with_replacement(range(1, M+1), r=N):
        t = 0
        for A, B, C, D in ABCD:
            if a[B-1] - a[A-1] == C:
                t += D
        ans = max(ans, t)
    return ans


def main():
    N, M, Q = read_int_n()
    ABCD = [read_int_n() for _ in range(Q)]
    print(slv(N, M, Q, ABCD))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import combinations_with_replacement


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


def slv(N, M, Q, ABCD):
    ans = 0
    for a in combinations_with_replacement(range(1, M+1), r=N):
        t = 0
        for abcd in ABCD:
            A, B, C, D = abcd
            if a[B-1] - a[A-1] == C:
                t += D
        ans = max(ans, t)
    return ans


def main():
    N, M, Q = read_int_n()
    ABCD = [read_int_n() for _ in range(Q)]
    print(slv(N, M, Q, ABCD))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
input = raw_input

#from copy import deepcopy

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

score_dict = {}

for i in range(1, n):
    for j in range(i+1, n+1):
        key = (i, j)
        score_dict[key] = []

As = []
def f(last_array, last_val, num):
    if num == n:
        As.append(last_array)
    else:
        for cur_val in range(last_val, m+1):
            cur_array = last_array + [cur_val]
            f(cur_array, cur_val, num+1)

f([1], 1, 1)

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

out = 0
for A in As:
    cur = 0
    for a, b, c, d in all_inputs:
        b -= 1
        a -= 1
        if c == A[b] - A[a]:
            cur += d
    out = max(cur, out)

print(out)

Submission status: Accepted

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

def input_one_number():
    return int(input())

def input_multiple_number():
    return map(int, input().split())

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


N,M,Q = input_multiple_number()

lists = []

for i in range(Q):
	lis = input_multiple_number_as_list()
	lists.append(lis)

ans = 0
import itertools
for a in itertools.combinations_with_replacement(range(1,M+1),N):
	score = 0
	for _q in lists:
		#a = [i,i2,i3,i4,i5,i6,i7,i8,i9,i10]
		if (a[_q[1]-1]-a[_q[0]-1]) == _q[2]:
			score += _q[3]
	ans = max(ans,score)
										
print(ans)

Submission status: Accepted

Solution code:
a = input().split()
N = int(a[0])
M = int(a[1])
Q = int(a[2])
current = []
for i in range(Q):
    e = input().split()
    f = [int(i) for i in e]
    current.append(f)
import itertools

c = list(itertools.combinations_with_replacement(range(1, M + 1), N))
value_list = []
for item in c:
    value = 0
    for k in current :
        if item[k[1]-1]-item[k[0]-1]==k[2]:
            value+=k[3]
    value_list.append(value)

print(max(value_list))

Submission status: Accepted

Solution code:
def calcP(l, abcd):
    p = 0
    for a, b, c, d in abcd:
        if l[b-1] - l[a-1] == c:
            p += d
    return p

def update(l, i, m, n):
    if i > n:
        return [m for _ in range(n)]

    if l[-i] == m:
        return update(l, i+1, m, n)

    l[-i] += 1
    for j in range(i-1):
        l[-i+j+1] = l[-i]
    return l

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

mp = 0
l = [1 for _ in range(n)]
while True:
    p = calcP(l, abcd)
    if p > mp:
        mp = p
    update(l, 1, m, n)
    if l == [m for _ in range(n)]:
        break

p = calcP(l, abcd)
if p > mp:
    mp = p

print(mp)

Submission status: Accepted

Solution code:
import sys
import itertools

N,M,Ql = map(int, sys.stdin.readline().strip().split())
Q = []
for _ in range(Ql):
    Q.append(list(map(int, sys.stdin.readline().strip().split())))

max = 0
for A in itertools.combinations_with_replacement(range(1,M+1), N):
    ans = 0
    for Qi in Q:
        a,b,c,d = Qi

        if (A[b-1] - A[a-1]) == c:
            ans += d
    if max < ans:
        max = ans

print(max)

Submission status: Accepted

Solution code:
from itertools import *

n = list(map(int,input().split()))
mm =[]
list1 = []
kei  = []

for x in range(n[2]):
    m = list(map(int,input().split()))
    mm.append(m)

for x in range(n[1]):
    list1.append(x+1)

a = list(combinations_with_replacement(list1,n[0]))

for x in range(len(a)):
    count = 0
    for l in range(n[2]):
        if a[x][int(mm[l][1]-1)] - a[x][int(mm[l][0]-1)] == int(mm[l][2]):
            count += int(mm[l][3])
    kei.append(count)

print(max(kei))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m,q = map(int,input().split())
chk = []
for i in range(q):
  a = [int(i) for i in input().split()]
  chk.append(a)

ans = 0
import itertools
for i in itertools.combinations_with_replacement(range(1, m+1), n):
  dd = 0
  for j in chk:
    a,b,c,d = j
    if i[a-1] + c == i[b-1]:
      dd += d
  ans = max(dd,ans)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as H
N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]
ret = []
for ls in list(H(range(1,M+1), N)):
    cand = 0
    for a,b,c,d in abcd:
        if ls[b-1] - ls[a-1] == c:
            cand += d
    ret.append(cand)
print(max(ret))

Submission status: Accepted

Solution code:
import itertools
 
def resolve():
    N, M, Q = map(int, input().split())
    a_list = []
    b_list = []
    c_list = []
    d_list = []
 
    for i in range(Q):
        a, b, c, d = map(int, input().split())
        a_list.append(a)
        b_list.append(b)
        c_list.append(c)
        d_list.append(d)

    ans = 0    
    for A in itertools.combinations_with_replacement(range(1,M+1),N):
        score = 0
        for i in range(Q):
            if A[b_list[i]-1] - A[a_list[i]-1] == c_list[i]:
                score += d_list[i]
        ans = max(score, ans)
    print(ans)

 
if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import numpy as np
import itertools

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

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

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

MAX=0

for al in all:
  sum=0
  for a,b,c,d in abcd:
    if al[b-1] - al[a-1] == c:
      sum += d
  MAX=max(sum,MAX)
  
print(MAX)

Submission status: Accepted

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


def dfs(x, s):
    if len(s) == n:
        ls.append(s)
        return 0
    else:
        for y in range(x, m):
            dfs(y, s+str(y))


dfs(0, "")
ans = 0
for x in ls:
    x = tuple(map(lambda x: int(x)+1, list(x)))
    cnt = 0
    for a, b, c, d in abcd:
        a -= 1
        b -= 1
        if x[b]-x[a] == c:
            cnt += d
    if ans < cnt:
        ans = cnt
print(ans)

Submission status: Accepted

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

def input_one_number():
    return int(input())

def input_multiple_number():
    return map(int, input().split())

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


N,M,Q = input_multiple_number()

lists = []

for i in range(Q):
	lis = input_multiple_number_as_list()
	lists.append(lis)

ans = 0
for i in range(1,M+1):
	for i2 in range(i,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):
										score = 0
										for _q in lists:
											a = [i,i2,i3,i4,i5,i6,i7,i8,i9,i10]
											if (a[_q[1]-1]-a[_q[0]-1]) == _q[2]:
												score += _q[3]
										ans = max(ans,score)
										
print(ans)

Submission status: Accepted

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

a=list(itertools.combinations_with_replacement([i for i in range(m)],n))
S=0
for j in range(len(a)):
    b=a[j]
    s=0
    for k in range(q):
        if b[l[k][1]-1]-b[l[k][0]-1]==l[k][2]:
            s+=l[k][3]
    S=max(s,S)
print(S)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

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

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

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

MAX=[]

for al in all:
  sum=0
  for a,b,c,d in abcd:
    if al[b-1] - al[a-1] == c:
      sum += d
  MAX.append(sum)
  
print(max(MAX))

Submission status: Accepted

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

ans = 0
for A in itertools.combinations_with_replacement(range(1,m+1),n):
    score = 0
    for i in range(q):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            score += d[i]
    ans = max(score,ans)
print(ans)

Submission status: Accepted

Solution code:
import itertools

N, M, Q = map(int, input().split())
abcd = []
for i in range(Q):
    *v, = map(int, input().split())
    abcd.append(v)

ans = 0
c = [i for i in range(1, M+1)]
for A in itertools.combinations_with_replacement(c, N):
    ta = 0
    for a, b, c, d in abcd:
        if (A[b-1]-A[a-1]) == c:
            ta += d
    if ans < ta:
        ans = ta

print(ans)

Submission status: Accepted

Solution code:
#dfs試す
n,m,q=map(int, input().split( ))
qs=tuple(tuple(map(int, input().split( ))) for _ in range(q))
def dfs(ll):
    if len(ll)==n+1:
        sm=0
        for ai,bi,ci,di in qs:
            if ll[bi]-ll[ai]==ci:
                sm+=di 
        return sm
    res=[]
    for i in range(ll[-1],m):#+1
        ll2=ll+[i]
        res.append(dfs(ll2))
    return(max(res))
l=[0]
print(dfs(l))

Submission status: Accepted

Solution code:
import itertools

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

a=[]
b=[]
c=[]
d=[]

for i in range(q):
    x = list(map(int, input().split()))
    a.append(x[0])
    b.append(x[1])
    c.append(x[2])
    d.append(x[3])

h = []
A_list = list(itertools.combinations_with_replacement(range(1, m+1), n))


for A in A_list:
    s = 0
    for i in range(q):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            s += d[i]
    h.append(s)

print(max(h))