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:
NMQ = list(map(int, input().split()))
N = NMQ[0]
M = NMQ[1]
Q = NMQ[2]
listOfLists = []
Qlist = []
for i in range(Q):
    Qlist.append(list(map(int, input().split())))
if N == 2:
    for a in range(1,M+1):
        for b in range(a,M+1):
            listOfLists.append([1,a,b,M])
if N == 3:
    for a in range(1,M+1):
        for b in range(a,M+1):
            for c in range(b,M+1):
                listOfLists.append([1,a,b,c,M])
if N == 4:
    for a in range(1,M+1):
        for b in range(a,M+1):
            for c in range(b,M+1):
                for d in range(c,M+1):
                    listOfLists.append([1,a,b,c,d,M])
if N == 5:
    for a in range(1,M+1):
        for b in range(a,M+1):
            for c in range(b,M+1):
                for d in range(c,M+1):
                    for e in range(d,M+1):
                        listOfLists.append([1,a,b,c,d,e,M])
if N == 6:
    for a in range(1,M+1):
        for b in range(a,M+1):
            for c in range(b,M+1):
                for d in range(c,M+1):
                    for e in range(d,M+1):
                        for f in range(e,M+1):
                            listOfLists.append([1,a,b,c,d,e,f,M])
if N == 7:
    for a in range(1,M+1):
        for b in range(a,M+1):
            for c in range(b,M+1):
                for d in range(c,M+1):
                    for e in range(d,M+1):
                        for f in range(e,M+1):
                            for g in range(f,M+1):
                                listOfLists.append([1,a,b,c,d,e,f,g,M])
if N == 8:
    for a in range(1,M+1):
        for b in range(a,M+1):
            for c in range(b,M+1):
                for d in range(c,M+1):
                    for e in range(d,M+1):
                        for f in range(e,M+1):
                            for g in range(f,M+1):
                                for h in range(g,M+1):
                                    listOfLists.append([1,a,b,c,d,e,f,g,h,M])
if N == 9:
    for a in range(1,M+1):
        for b in range(a,M+1):
            for c in range(b,M+1):
                for d in range(c,M+1):
                    for e in range(d,M+1):
                        for f in range(e,M+1):
                            for g in range(f,M+1):
                                for h in range(g,M+1):
                                    for i in range(h,M+1):
                                        listOfLists.append([1,a,b,c,d,e,f,g,h,i,M])
if N == 10:
    for a in range(1,M+1):
        for b in range(a,M+1):
            for c in range(b,M+1):
                for d in range(c,M+1):
                    for e in range(d,M+1):
                        for f in range(e,M+1):
                            for g in range(f,M+1):
                                for h in range(g,M+1):
                                    for i in range(h,M+1):
                                        for j in range(i,M+1):
                                            listOfLists.append([1,a,b,c,d,e,f,g,h,i,j,M])
scoreList = []
def cal_score(a,b):
    score = 0
    if a[b[1]] - a[b[0]] == b[2]:
        score = b[3]
    return score

for item in listOfLists:
    setResult = []
    for j in Qlist:
        setResult.append(cal_score(item,j))
    scoreList.append(sum(setResult))
print(max(scoreList))

Submission status: Accepted

Solution code:
def resolve():
    n, m, q = map(int, input().split())
    queue = []
    for i in range(q):
        queue.append(list(map(int, input().split())))
    ans = 0
    import itertools
    l = itertools.combinations(range(1, n + m), n)
    for i in l:
        a = [x - y for y, x in enumerate(i)]
        x = 0
        for j in queue:
            if a[j[1] - 1] - a[j[0] - 1] == j[2]:
                x += j[3]
        ans = max(ans, x)
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

A_list = list(itertools.combinations_with_replacement(range(1,M+1),N))
#print(A_list)
score_max=0
for A in A_list:
    score = 0
#    print("A=",A)
    for row in abcd :
#        print("row=",row)
        if A[row[1]-1]-A[row[0]-1]==row[2]:
#            print('get')
            score += row[3]
    if score > score_max:
            score_max = score
#            print('max_revised: ', score_max)
    else:
        pass
print(score_max)

Submission status: Accepted

Solution code:
def abc165_c():
  n, m, q = map(int, input().split())
  query = [tuple(map(int, input().split())) for _ in range(q)]
  ans = 0

  def dfs(arr):
    # 得点計算
    if len(arr) == n:
      calc_score(arr)
      return
    # それ以外は後ろに追加して次へ
    if len(arr) == 0: start = 1
    else: start = arr[-1]
    for i in range(start, m+1):
      dfs(arr + [i])

  def calc_score(arr):
    nonlocal ans
    score = 0
    for a, b, c, d in query:
      if arr[b-1] - arr[a-1] == c:
        score += d
    if score > ans: ans = score

  dfs([])
  print(ans)

abc165_c()

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)

def calc_ans(x,A,B,C,D):
    #print(x)
    ans = 0
    for i in range(len(A)):
        if x[B[i]-1] - x[A[i]-1] == C[i]:
            ans += D[i]
    return ans

# x = [1] * n

# for i in range(1, n):
#     for j in range(x[i], m):

answers = {}

l = list(range(m))
for v in itertools.combinations_with_replacement(l, n):
    v = sorted(v)
    vs = ''.join(str(v))
    if vs in answers.keys():
        pass
    else:
        ans = calc_ans(v,A,B,C,D)
        answers[vs] = ans
#print(answers.values())
print(max(answers.values()))

Submission status: Accepted

Solution code:
import itertools

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

for v in itertools.combinations_with_replacement(range(1, m+1), n):
  tmp = 0
  for i in range(q):
    if v[s[i][1]-1] - v[s[i][0]-1] == s[i][2]:
      tmp += s[i][3]
  ans.append(tmp)
  
print(max(ans))

Submission status: Accepted

Solution code:
import itertools
n, m, q = map(int, input().split())
s = []
for i in range(q):
    s.append(list(map(int, input().split())))
a = list(itertools.combinations_with_replacement(range(1, m+1), n))
max_d = 0
for A in a:
    sum_d = 0
    for li in s:
        if A[li[1]-1] - A[li[0]-1] == li[2]:
            sum_d += li[3]
    max_d = max(max_d, sum_d)
print(max_d)

Submission status: Accepted

Solution code:
from itertools import combinations

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

ans = 0
List = []
for i in range(Q):
    List.append(tuple(map(int, input().split())))

List2 = []
for i in range(N + M - 1):
    List2.append(i)


for x in combinations(List2, M - 1):
    List3 = [1] * N
    n = 0
    an = 0
    for y in x:
        y -= n
        for iii in range(y, N):
            List3[iii] += 1
        n += 1
    for i in range(Q):
        a, b, c, d = List[i]
        if List3[b-1] - List3[a-1] == c:
            an += d
    ans = max(ans, an)

print(ans)

Submission status: Accepted

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

def main():
    n, m, q = map(int, input().split())
    arrys = [list(map(int, input().split())) for _ in range(q)]
    
    a = list(range(1, m+1))
    a_lists = list(itertools.combinations_with_replacement(a, n))
    score = 0
    
    for a_list in a_lists:
        tmp_score = 0
        for arry in arrys:
            if a_list[arry[1]-1] - a_list[arry[0]-1] == arry[2]:
                tmp_score += arry[3]
        score = max(score, tmp_score)
    print(score)



    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
N, M, Q = map(int, input().split())
ABCD = []
for _ in range(Q):
    ABCD.append(list(map(int, input().split())))
ref = list(range(1, M+1))
all_candidate = list(combinations_with_replacement(ref, N))
ans = 0
for candidate in all_candidate:
    point = 0
    for abcd in ABCD:
        if candidate[abcd[1]-1] - candidate[abcd[0]-1] == abcd[2]:
            point += abcd[3]
    ans = max(ans, point)
print(ans)

Submission status: Accepted

Solution code:
import itertools
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])    
ans=0
for i in range(m):
    L=[i for i in range(1,n+i-1)]
    C=itertools.combinations(L,n-2)
    for c in C:
        #print(c)
        cnt=0
        A=[1]
        now=0
        for j in range(n-2):
            A.append(A[-1]+c[j]-now-1)
            now=c[j]
        A.append(i+1)
        #print(A)
        for que in Q:
            if A[que[1]]-A[que[0]]==que[2]:
                cnt+=que[3]
        ans=max(cnt,ans)
print(ans)

Submission status: Accepted

Solution code:
import itertools
n, m, q = map(int, input().split())
comb = itertools.combinations_with_replacement(range(1, m+1), n)
a = []
b = []
c = []
d = []
score = 0
for _ in range(q):
    ai, bi, ci, di = map(int, input().split())
    a.append(ai)
    b.append(bi)
    c.append(ci)
    d.append(di)
for cmb in comb:
    cnt = 0
    for ai, bi, ci, di in zip(a, b, c, d):
        if cmb[bi-1] - cmb[ai-1] == ci:
            cnt += di
    score = max(score, cnt)
print(score)

Submission status: Accepted

Solution code:
import itertools

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

l = [1, 2, 3, 4]
l = [m for m in range(1, m + 1)]

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

# print(ql)

max_s = 0
for v in itertools.combinations_with_replacement(l, n):
    # print(v)
    score = 0
    for qq in ql:
        a, b, c, d = qq
        # print("{} - {} = {}".format(v[b], v[a], c))
        if v[b] - v[a] == c:
            score += qq[3]
            
    # print(score)
    if score > max_s:
        max_s = score
        
print(max_s)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**9)

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

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

def recu(l):
    global ans
    if len(l) == N:
        # dの総和を計算
        tmp = 0
        for j in range(Q):
            if l[b[j]-1] - l[a[j]-1] == c[j]:
                tmp += d[j]
        ans = max(ans, tmp)
    else:
        for i in range(l[-1],M+1):
            recu(l + [i])

def main():
    
    l = [1]
    recu(l)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()

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


nlst=[[1]]
while len(nlst[0])<N:
    lst=nlst
    nlst=[]
    while lst:
        l=lst.pop()

        for i in range(l[-1],M+1):
            ll=copy.copy(l)
            ll.append(i)
            nlst.append(ll)
#print(nlst)
ans=0
for lst in nlst:
    value=0
    for a,b,c,d in ABCD:
        if lst[b-1]-lst[a-1]==c:
            value+=d
    ans=max(ans,value)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools

n,m,q=map(int,input().split())
List=[]
for i in range(m):
    List.append(i+1)
ans=[0,0]
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())
    
for v in itertools.combinations_with_replacement(List,n):
    ans[0]=0
    #print(v)
    for i in range(q):
        if (v[b[i]-1]-v[a[i]-1]==c[i]):
            ans[0]+=d[i]
           # print("Got",a[i],b[i],c[i],d[i])
    #print(ans[0])
    ans[1]=max(ans[1],ans[0])
    
print(ans[1])

Submission status: Accepted

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

if n == 2:
    for i1 in range(1, m + 1):
        for i2 in range(i1, m + 1):
            l = [i1, i2]
            v = 0
            for j in x:
                if l[j[1] - 1] - l[j[0] - 1] == j[2]:
                    v += j[3]
            ans = max(ans, v)
elif n == 3:
    for i1 in range(1, m + 1):
        for i2 in range(i1, m + 1):
            for i3 in range(i2, m + 1):
                l = [i1, i2, i3]
                v = 0
                for j in x:
                    if l[j[1] - 1] - l[j[0] - 1] == j[2]:
                        v += j[3]
                ans = max(ans, v)
elif n == 4:
    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):
                    l = [i1, i2, i3, i4]
                    v = 0
                    for j in x:
                        if l[j[1] - 1] - l[j[0] - 1] == j[2]:
                            v += j[3]
                    ans = max(ans, v)
elif n == 5:
    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):
                        l = [i1, i2, i3, i4, i5]
                        v = 0
                        for j in x:
                            if l[j[1] - 1] - l[j[0] - 1] == j[2]:
                                v += j[3]
                        ans = max(ans, v)
elif n == 6:
    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):
                            l = [i1, i2, i3, i4, i5, i6]
                            v = 0
                            for j in x:
                                if l[j[1] - 1] - l[j[0] - 1] == j[2]:
                                    v += j[3]
                            ans = max(ans, v)
elif n == 7:
    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):
                                l = [i1, i2, i3, i4, i5, i6, i7]
                                v = 0
                                for j in x:
                                    if l[j[1] - 1] - l[j[0] - 1] == j[2]:
                                        v += j[3]
                                ans = max(ans, v)
elif n == 8:
    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):
                                    l = [i1, i2, i3, i4, i5, i6, i7, i8]
                                    v = 0
                                    for j in x:
                                        if l[j[1] - 1] - l[j[0] - 1] == j[2]:
                                            v += j[3]
                                    ans = max(ans, v)
elif n == 9:
    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 = [i1, i2, i3, i4, i5, i6, i7, i8, i9]
                                        v = 0
                                        for j in x:
                                            if l[j[1] - 1] - l[j[0] - 1] == j[2]:
                                                v += j[3]
                                        ans = max(ans, v)
else:
    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):
                                            l = [i1, i2, i3, i4, i5, i6, i7, i8, i9, i10]
                                            v = 0
                                            for j in x:
                                                if l[j[1] - 1] - l[j[0] - 1] == j[2]:
                                                    v += j[3]
                                            ans = max(ans, v)

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

p = itertools.product(l, repeat=n)
p = itertools.combinations_with_replacement(l, n)
list_p = list(p)
cmb = []
for p in list_p:
  cmb.append(list(p))



ans = 0

# 処理系
for cm in cmb:
  tmp = 0
  for d in data:
    b_point = d[1]
    a_point = d[0]
    c_point = d[2]
    d_point = d[3]
    if cm[b_point - 1] - cm[a_point - 1] == c_point:
      tmp += d_point

  ans = max(ans, tmp)


print(ans)

Submission status: Accepted

Solution code:

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


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

A=[]

if N==10:
    for a in range(1, M + 1):
        for b in range(a, M + 1):
            for c in range(b, M + 1):
                for d in range(c, M + 1):
                    for e in range(d, M + 1):
                        for f in range(e, M + 1):
                            for g in range(f, M + 1):
                                for h in range(g, M + 1):
                                    for i in range(h, M + 1):
                                        for j in range(i, M + 1):
                                            A.append([a, b, c, d, e, f, g, h, i, j])

elif N==9:
    for a in range(1, M + 1):
        for b in range(a, M + 1):
            for c in range(b, M + 1):
                for d in range(c, M + 1):
                    for e in range(d, M + 1):
                        for f in range(e, M + 1):
                            for g in range(f, M + 1):
                                for h in range(g, M + 1):
                                    for i in range(h, M + 1):
                                        A.append([a, b, c, d, e, f, g, h, i])

elif N==8:
    for a in range(1, M + 1):
        for b in range(a, M + 1):
            for c in range(b, M + 1):
                for d in range(c, M + 1):
                    for e in range(d, M + 1):
                        for f in range(e, M + 1):
                            for g in range(f, M + 1):
                                for h in range(g, M + 1):
                                    A.append([a, b, c, d, e, f, g, h])

elif N == 7:
    for a in range(1, M + 1):
        for b in range(a, M + 1):
            for c in range(b, M + 1):
                for d in range(c, M + 1):
                    for e in range(d, M + 1):
                        for f in range(e, M + 1):
                            for g in range(f, M + 1):
                                A.append([a, b, c, d, e, f, g])

elif N == 6:
    for a in range(1, M + 1):
        for b in range(a, M + 1):
            for c in range(b, M + 1):
                for d in range(c, M + 1):
                    for e in range(d, M + 1):
                        for f in range(e, M + 1):
                            A.append([a, b, c, d, e, f])

elif N == 5:
    for a in range(1, M + 1):
        for b in range(a, M + 1):
            for c in range(b, M + 1):
                for d in range(c, M + 1):
                    for e in range(d, M + 1):
                        A.append([a, b, c, d, e])

elif N == 4:
    for a in range(1, M + 1):
        for b in range(a, M + 1):
            for c in range(b, M + 1):
                for d in range(c, M + 1):
                    A.append([a, b, c, d])

elif N == 3:
    for a in range(1, M + 1):
        for b in range(a, M + 1):
            for c in range(b, M + 1):
                A.append([a, b, c])

elif N == 2:
    for a in range(1, M + 1):
        for b in range(a, M + 1):
            A.append([a, b])

d=[0]*len(A)
for s in range(len(A)):
    for i in range(Q):
        if A[s][S[i][1]-1]-A[s][S[i][0]-1]==S[i][2]:
            d[s]=d[s]+S[i][3]

print(max(d))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys
from collections import Counter
from itertools import permutations, combinations_with_replacement
#from fractions import gcd
from math import gcd
from math import ceil, floor
import bisect
sys.setrecursionlimit(10 ** 6)
inf = float("inf")

def input():
    return sys.stdin.readline()[:-1]

def main():
    n, m, q = map(int, input().split())
    abcd = [None] * q
    for i in range(q):
        abcd[i] = tuple(map(int, input().split()))

    A = list(range(m))
    ans = 0
    comb = list(combinations_with_replacement(A, n))
    for c in comb:
        tmp_ans = 0
        for i in range(q):
            if c[abcd[i][1]-1] - c[abcd[i][0]-1] == abcd[i][2]:
                tmp_ans += abcd[i][3]
        ans = max(ans, tmp_ans)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
q_list=[]
for i in range(q):
    a=list(map(int,input().split()))
    q_list.append(a)
import itertools
ans=0
for i in itertools.combinations_with_replacement(range(1,m+1),n):
#     i=sorted(i)
    count=0
    for a,b,c,d in q_list:
        if i[b-1]-i[a-1]==c:
            count+=d

    ans=max(count,ans)
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

ans = 0

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

for a in arrs:
  _sum = 0
  a = list(a)
  for b in arr:
    if a[b[1]-1]-a[b[0]-1]==b[2]:
      _sum += b[3]
  ans = max(ans,_sum)
  
  
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import itertools
#sys.setrecursionlimit(150000)

def chkA(A, Q, a, b, c, d):
    ret=0
    for i in range(Q):
        ret += d[i] if A[b[i]-1] - A[a[i]-1] == c[i] else 0
    return ret
            

def solve(N: int, M: int, Q: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
    P=[i+1 for i in range(M+N-1)]
    B=[0]*N
    ans=0
    for A in itertools.combinations(P, N):
        for i in range(N):
            B[i]=A[i]-i
        ans = max(ans, chkA(B, Q, a, b, c, d))
    print(ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    a = [int()] * (Q)  # type: "List[int]"
    b = [int()] * (Q)  # type: "List[int]"
    c = [int()] * (Q)  # type: "List[int]"
    d = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
        d[i] = int(next(tokens))
    solve(N, M, Q, a, b, c, d)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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)

import itertools
ANS = []
for i in list(itertools.combinations_with_replacement([i for i in range(1, m+1)], n)):
    L = list(i)
    t = 0
    for i in range(q):
        if L[B[i] - 1] - L[A[i] - 1] == C[i]:
            t += D[i]
    ANS.append(t)

print(max(ANS))

Submission status: Accepted

Solution code:

import itertools


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

choices = list(itertools.combinations_with_replacement([i for i in range(1, m+1)], n))
ans = -1
for choice in choices:
    score = 0
    for q in query:
        if choice[q[1]-1] - choice[q[0]-1] == q[2]:
            score += q[3]
    ans = max(ans, score)
print(ans)

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
abc=[]
def f(L):
    v=0
    for a,b,c,d in abc:
        #print(L[b-1],L[a-1],c)
        if L[b-1]-L[a-1] !=c:
            pass
        else:
            v+=d
    else:
        return v
def gen(ls):
    res=[]
    for l in ls:
        for j in range(l[-1],m+1):
            ll = l.copy()
            ll.append(j)
            res.append(ll)
    return res

for _ in range(q):
    a,b,c,d=map(int,input().split())
    abc.append((a,b,c,d))
K = [[1]]
for _ in range(n-1):
    K = gen(K)
max_=0
for k in K:
    max_=max(max_,f(k))
print(max_)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

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

    data = [[1]]
    for _ in range(N):
        tmp = []
        for d in data:
            v = d[-1]
            for m in range(M):
                if v + m > M:
                    break
                tmp.append(d + [v + m])
        data = tmp

    ans = 0
    for val in data:
        tmp_ans = 0
        for a, b, c, d in abcd:
            if val[b - 1] - val[a - 1] == c:
                tmp_ans += d
        if tmp_ans > ans:
            ans = tmp_ans
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import itertools

def solve(N: int, M: int, Q: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
    l = list(range(N+M-1))
    max_score = 0
    for comb in itertools.combinations(l, M-1):
        A = []
        n = 1
        for i in range(N+M-1):
            if i in comb:
                n+=1
            else:
                A.append(n)
        #print(A)
        score = sum([di if A[bi-1] - A[ai-1] == ci else 0 for ai, bi, ci, di in zip(a, b, c, d)])
        max_score = max(score, max_score)

    print(max_score)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    a = [int()] * (Q)  # type: "List[int]"
    b = [int()] * (Q)  # type: "List[int]"
    c = [int()] * (Q)  # type: "List[int]"
    d = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
        d[i] = int(next(tokens))
    solve(N, M, Q, a, b, c, d)

if __name__ == '__main__':
    main()

Submission status: Accepted

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


ans =list(combinations_with_replacement(range(1,M+1),N))
x=[]
for i in range(len(ans)):
  kz=0
  a = list(ans[i])
  for j in range(Q):
    if a[(abcd[j][1])-1] - a[(abcd[j][0])-1] == abcd[j][2]:
      kz += abcd[j][3]
    else:
      continue
  x.append(kz)
  
x.sort()

print(x[-1])

Submission status: Accepted

Solution code:
import itertools
import numpy as np

N, M, Q = map(int, input().split())
grid = []
for i in range(Q):
    array = list(map(int, input().strip().split()))
    grid.append(array)

l = np.arange(1, M + 1)
max = 0
temp = 0

for c in itertools.combinations_with_replacement(l, N):
    for d in grid:
        if c[d[1]-1] - c[d[0]-1] == d[2]:
            temp += d[3]
    if max < temp:
        max = temp
    temp = 0

print(max)

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

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

tmp = []
for v in hoge:
    sum = 0
    for i in range(Q):
        if v[b[i] - 1] - v[a[i] - 1] == c[i]:
            sum += d[i]

    tmp.append(sum)

print(max(tmp))

Submission status: Accepted

Solution code:
import itertools

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

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

result=[]

for j in li:
    ans=0
    for k in abcd:
        t1=k[1]-1
        t2=k[0]-1
        if j[t1]-j[t2]==k[2]:
            ans+=k[3]
    else:
        result.append(ans)

print(max(result))

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)]
c = [i for i in range(1, m+1)]

i = list(itertools.combinations_with_replacement(c, n))

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

print(ans)