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, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M, Q = MAP()
L = [LIST() for i in range(Q)]

ans = 0
A_list = list(combinations_with_replacement(range(1, M+1), N))
for A in A_list:
    tmp = 0
    for a, b, c, d in L:
        if A[b-1] - A[a-1] == c:
            tmp += d
    ans = max(tmp,ans)
print(ans)

Submission status: Accepted

Solution code:
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:
import itertools
N, M, Q = map(int,input().split())
L = []
for _ in range(Q):
    L.append(list(map(int,input().split())))

A = itertools.combinations_with_replacement([i for i in range(1,M+1)], N)
count = []
for a in A:
    temp = 0
    for l in L:
        if a[l[1]-1] - a[l[0]-1] == l[2]:
            temp += l[3]
    count.append(temp)
print(max(count))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter

from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
#dequeを使うときはpython3を使う、pypyはダメ
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds

#mod = 10**9+7
#w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

#N = int(input())
N, M, Q = map(int, input().split())
L = [list(map(int, input().split())) for i in range(Q)]
#A = list(map(int, input().split()))
l=[1]*N

def next(i):
    if i==N-1:
        if l[i]==M:
            return True
        else:
            l[i]+=1
            return False
    x=next(i+1)
    if x:
        if l[i]==M:
            return True
        else:
            lp=l[i]+1
            for j in range(i,N):
                l[j]=lp
            return False
    else: return False

def score(l):
    sc=0
    for z in L:
        a,b,c,d=z[0],z[1],z[2],z[3]
        if l[b-1]-l[a-1]==c:
            sc+=d
    return sc

b=False
ans=0
while b==False:
    ans=max(ans,score(l))
    b=next(0)
print(ans)

Submission status: Accepted

Solution code:
import math
import pprint
import fractions
import collections
import itertools
N,M,Q=map(int,input().split())
req=[list(map(int,input().split())) for _ in range(Q)]
seq=list(range(1,M+1))
l=list(itertools.combinations_with_replacement(seq,N))
#print(l)
score=0
maxscore=0
buf=[]
for i in range(len(l)):
    score=0
    buf=list(l[i])
    for j in range(Q):
        left,right,dist,num=map(int,req[j])
        left=left-1
        right=right-1
        if buf[right]-buf[left]==dist:
            score=score+num
    maxscore=max(score,maxscore)
print(maxscore)

Submission status: Accepted

Solution code:

lis = []
res = 0


def solve():

    N, M, Q = map(int, input().split())
    e = [list(map(int, input().split())) for i in range(Q)]
    global lis
    lis = [0]*N

    def dfs(x, y):
        global lis, res
        if x == N:
            tmp = 0
            for a, b, c, d in e:
                if lis[b-1]-lis[a-1] == c:
                    tmp += d
            res = max(res, tmp)
            return

        for i in range(y, M+1):
            lis[x] = i
            dfs(x+1, i)

    dfs(0, 1)
    print(res)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np
from itertools import *


def solve(N: int, M: int, Q: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
    l = [i for i in range(1,M+1)]
    ans = 0
    for v in combinations_with_replacement(l, N):
        score = 0
        for j in range(Q):
            #print(a[j],b[j],c[j],d[j],A[i][b[j]-1]-A[i][a[j]-1], c[j], d[j])
            #print(A[i][b[j]-1]-A[i][a[j]-1], c[j])
            if (v[b[j]-1]-v[a[j]-1])==c[j]:
                score += d[j]
        #print(ans[i])
        ans = max(ans, score)
    #print(ans)
    print(ans)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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 = [int(i) for i in input().split(" ")]
A = []
for i in range(Q):
    a = [int(i) for i in input().split(" ")]
    A.append(a)

ans = 0

for i in combinations_with_replacement(range(1,M+1),N):
    tmp_ans = 0
    for j in A:
        if i[j[1] - 1] - i[j[0] - 1] != j[2]:
            continue
        tmp_ans += j[3]

    if ans < tmp_ans:
        ans = tmp_ans

print(ans)

Submission status: Accepted

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

    ans = 0
    for sequence in combinations_with_replacement(range(1, M + 1), N):
        score = 0
        for a, b, c, d in Queries:
            a, b = a - 1, b - 1
            if sequence[b] - sequence[a] == c:
                score += d
        ans = max(ans, score)
    return ans

print(c_many_requirements())

Submission status: Accepted

Solution code:
import itertools
N, M, Q = map(int,input().split())
s = [tuple(map(int, input().split())) for i  in range(Q)]
l = list(range(1,M+1))
ans = [0]
for v in itertools.combinations_with_replacement(l, N):
    count = 0
    for i in range(Q):
        a, b, c, d = s[i]
        if v[b-1] - v[a-1] == c:
            count += d
    ans.append(count)
print(max(0, max(ans)))

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 i in range(Q)]
#ABCD = sorted(ABCD, key = lambda x: x[3], reverse = True)

def score(A, ABCD):
  ans = 0
  for i in range(Q):
    x = ABCD[i]
    if A[x[1] - 1] - A[x[0] - 1] == x[2]:
      ans += x[3]
  return ans


b = []
for i in range(M):
  b.append(i + 1)
  
A = list(combinations_with_replacement(b, N))

ans = 0
for i in A:
  B = list(i)
  ans = max(ans, score(B, ABCD))
print(ans)

Submission status: Accepted

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

A,B,C,D=[0]*Q,[0]*Q,[0]*Q,[0]*Q
for i in range(Q):
    A[i],B[i],C[i],D[i]=map(int,input().split())
    A[i]-=1
    B[i]-=1

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

ans=0
for a in itertools.combinations_with_replacement(num,N):
    tmp_sum=0
    for i in range(Q):
        if a[B[i]]-a[A[i]]==C[i]:
            tmp_sum+=D[i]
    ans=max(ans,tmp_sum)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as CwR

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

A = list(CwR(range(1,M+1),N))
lis = list()
for i in range(Q):
    a,b,c,d = map(int,input().split())
    a,b = a-1,b-1
    lis.append([a,b,c,d])

ans = 0
for A_ in A:
    tmp = 0
    for a,b,c,d in lis:
        if A_[b] - A_[a] == c:
            tmp += d
    ans = max(ans,tmp)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat May  2 22:58:08 2020

@author: Kei
"""

import numpy as np
import itertools

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

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


#s = [[0]*4]*Q
a = [0]*Q
b = [0]*Q
c = [0]*Q
d = [0]*Q

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

max_point = 0
    
for i in range(0,len(A)):
    point = 0
    for j in range (0,Q):
        if A[i][b[j]-1]-A[i][a[j]-1] == c[j]:
            point += d[j]
    max_point = max(point,max_point)
    

#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
#        
print(max_point)

Submission status: Accepted

Solution code:
import itertools
N, M, Q = map(int,input().split())
s = [tuple(map(int, input().split())) for i  in range(Q)]
l = list(range(1,M+1))
ans = []
for v in itertools.combinations_with_replacement(l, N):
    count = 0
    for i in range(Q):
        a, b, c, d = s[i]
        if v[b-1] - v[a-1] == c:
            count += d
    ans.append(count)
print(max(ans))

Submission status: Accepted

Solution code:

#長さN
#各値はM以下
n,m,q=map(int,input().split())

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

ai=set([])

def zentan(ss,x,i):
    #x以上
    global n,m,ai
    if i==n-1:
        for j in range(x,m):
            ai.add(ss+str(j))
    else:
        for j in range(x,m):
            zentan(ss+str(j),j,i+1)

result=0
zentan("",0,0)


for item in ai:
    point=0
    checked=[0]*n
    for item2 in abcd:
        
        a,b,c,d=item2[0]-1,item2[1]-1,item2[2],item2[3]
        if int(item[a])+c==int(item[b]):
            point+=d
    result=max(result,point)

print(result)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product
import sys
import bisect
import string
import math
import time



def I(): return int(input())


def S(): return input()


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


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def debug(table, *args):
    ret = []
    for name, val in table.items():
        if val in args:
            ret.append('{}: {}'.format(name, val))
    print(' | '.join(ret), file=sys.stderr)


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True

def rec(li, i, M, N, a, b, c, d, cans):
    # print(i, li, len(li), N)
    if len(li) >= N:
        # print(li, N)
        ans = 0
        for j in range(len(a)):
            if li[b[j]-1] - li[a[j]-1] == c[j]:
                ans += d[j]
        # print(ans, li)
        return ans

    # for j in range(1, len(lis[i])):
    #     for v in lis[i][j]:

    ans = 0
    if len(cans[i]) == 0:
        ans = max(ans, rec(li + [1], i+1, M, N, a, b, c, d, cans))
    else:
        for v in cans[i]:
            ans = max(ans, rec(li + [v], i+1, M, N, a, b, c, d, cans))

    return ans


def main():
    N, M, Q = MI()
    a = [0] * Q
    b = [0] * Q
    c = [0] * Q
    d = [0] * Q
    didx = [None] * Q
    lis = [[[] for i in range(N+1)] for i in range(N+1)]
    cans = [set() for i in range(N+1)]

    for i in range(Q):
        a[i], b[i], c[i], d[i] = MI()
        # didx[i] = (d[i], i)

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def make_a(n, M, L):
    if n == 0:
        return L
    W = len(L[0])
    newL = []
    for l in L:
        for i in range(l[W - 1], M + 1):
            newL += [list(l + [i])]
    return make_a(n - 1, M, newL)

def calc(N, M, Q, R):
    result = 0
    for A in make_a(N - 1, M, [[1]]):
        score = 0
        for a, b, c, d in R:
            score += (d if A[b - 1] - A[a - 1] == c else 0)
        result = max(score, result)
    return result


(N, M, Q) = tuple([int(s) for s in input().split()])
R = [tuple([int(s) for s in input().split()]) for _ in range(Q)]
print(calc(N, M, Q, R))

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())
  a[i], b[i] = a[i]-1, b[i]-1

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

print(ans)

Submission status: Accepted

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

max_ans = 0


def dfs(s):
    global max_ans
    if len(s) < N:
        for i in range(s[-1], M + 1):
            dfs(s + [i])
    else:
        ans = 0
        for a, b, c, d in reqs:
            a -= 1
            b -= 1
            if s[b] - s[a] == c:
                ans += d
        max_ans = max(max_ans, ans)


for j in range(M):
    dfs([j + 1])
print(max_ans)

Submission status: Accepted

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

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

def dfs(A, max_a):
    if len(A) == N:
        num = 0
        for a, b, c, d in conditions:
            if A[b-1] - A[a-1] == c:
                num += d
        return num
    ans = 0
    for i in range(max_a, M+1):
        ans = max(ans, dfs(A + [i], i))
    return ans

print(dfs([1], 1))

Submission status: Accepted

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

ls = list(range(n + m - 1))
mx = 0
for l in itertools.combinations(ls, m - 1):
    a = [0]
    idx = 0
    val = 1
    for i in range(n + m - 1): 
        if idx < m - 1 and i == l[idx]:
            val += 1
            idx += 1
        else: 
            a.append(val)
    #print(l, a)
    v = 0
    for i in query:
        if a[i[1]] - a[i[0]] == i[2]: v += i[3]
    mx = max(v, mx)
print(mx)

Submission status: Accepted

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

from collections import namedtuple
Val = namedtuple('val', ('a', 'b', 'c', 'd'))
vals = []
for _ in range(q):
    a,b,c,d = map(int, input().split())
    vals.append(Val(a, b, c, d))

import itertools

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

totals = [(0, 0)]
for combi in list(combis):

    total = 0
    combi1 = sorted(combi)
    for val in vals:
        cDiff = combi1[val.b - 1] - combi1[val.a - 1]
        if cDiff == val.c:
            total += val.d

    totals.append((total, combi1))

maxT = max(totals, key= lambda x: x[0])

print(maxT[0])

Submission status: Accepted

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

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

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

max_point = 0
for t in all_lists:
  point = 0
  for p in point_list:
    a, b, c, d = p
    if t[ b - 1 ] - t[ a - 1 ] == c:
      point += d
  max_point = max( max_point, point )
print( max_point )

Submission status: Accepted

Solution code:
n,m,q=list(map(int, input().split()))
conditions=[]
for i in range(q):
    conditions.append(list(map(int, input().split())))
max=0
for i0 in range(1,m+1):
    for i1 in range(i0, 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):
                                        a=[i0,i1,i2,i3,i4,i5,i6,i7,i8,i9]
                                        score=0
                                        for condition in conditions:
                                            if(a[condition[1]-1]-a[condition[0]-1]==condition[2]):
                                                score+=condition[3]
                                        if score>max:
                                            max=score

print(max)

Submission status: Accepted

Solution code:
import itertools
N, M, Q = map(int, input().split())
A = []
for i in range(0, Q):
        a, b, c, d = map(int,input().split())
        A.append([a,b,c,d])

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

ans_l = [0]
for A_n in itertools.combinations_with_replacement(nums, N):
        # print(A_n)
        ans = 0
        for i in range(0, Q):
                if A_n[(A[i][1] - 1)] - A_n[(A[i][0] - 1)] == A[i][2]:
                        # print(A_n[(A[i][1] - 1)], A_n[(A[i][0] - 1)], A[i][2], A[i][3])
                        ans += A[i][3]
        ans_l.append(ans)

# print(ans_l)
print(max(ans_l))

Submission status: Accepted

Solution code:
from collections import defaultdict

import itertools

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

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

ans = 0
for i in a:
  prs = 0
  for a, b, c, d in ABCD:
    if i[b - 1] - i[a - 1] == c:
      prs += d
  ans = max(ans, prs) 

print(ans)

Submission status: Accepted

Solution code:
N,M,Q=map(int,input().split(' '))
abcd = [list(map(int,input().split(' '))) for i in range(Q)]
def bfs(n,l):
    if n==N:
        res = 0
        for i in abcd:
            a,b,c,d=i
            if l[b-1]-l[a-1]==c:
                res += d
        return res
    else:
        return max([bfs(n+1,l+[i]) for i in range(l[-1],M+1)])
ans = 0
for i in range(1,M+1):
    ans = max(ans,bfs(1,[i]))
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

comb = list(itertools.combinations_with_replacement(range(1, m+1), n))
sum_d = 0
for c in comb:
    tmp = 0
    for a in abcd:
        if(c[a[1]-1] - c[a[0]-1] == a[2]):
            tmp += a[3]
    sum_d = max(tmp, sum_d)

print(sum_d)

Submission status: Accepted

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

from itertools import combinations_with_replacement

n, m, q = map(int, readline().split())
abcd = [list(map(int, readline().split())) for _ in range(q)]
ans = 0
for seq in combinations_with_replacement(range(m), n):
    cnt = 0
    for a, b, c, d in abcd:
        if seq[b - 1] - seq[a - 1] == c:
            cnt += d
    ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations_with_replacement

read = sys.stdin.read
readline = sys.stdin.readline

N, M, Q, *abcd = map(int, read().split())

answer = 0
abcd = tuple(zip(*[iter(abcd)] * 4))
for seq in combinations_with_replacement(range(1, M + 1), N):
    t = 0
    for a, b, c, d in abcd:
        if seq[b - 1] - seq[a - 1] == c:
            t += d
    answer = max(answer, t)

print(answer)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
import itertools

def input():
    return sys.stdin.readline()


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

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

    ans_dic = {}
    for combi in combi_list:
        ans_dic[str(combi)] = 0

    for combi in combi_list:

        for i, a_d in enumerate(a_d_list):
            a = a_d[0]
            b = a_d[1]
            c = a_d[2]
            d = a_d[3]

            if combi[b-1] - combi[a-1] == c:

                ans_dic[str(combi)] += d


    print(max(ans_dic.values()))





if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import itertools
def main():
    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])
    A = [i for i in range(1,M+1)]
    # if N==10:
    #
    #     ans = 0
    #     for i, qq in enumerate(q):
    #         if A[qq[1]] - A[qq[0]] == qq[2]:
    #             ans += qq[3]
    #     print(ans)
    #
    # else:
    aa = list(itertools.combinations_with_replacement(A,N))
    ans = 0

    for i, cc in enumerate(aa):
        ans1 = 0
        for j, qq in enumerate(q):
            if cc[qq[1]] - cc[qq[0]] == qq[2]:
                ans1 += qq[3]
            # print(ans1,cc)
        ans = max(ans,ans1)
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

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

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

saidai = 0
for c in comb:
    score = 0
    for a in A:
        if (c[a[1] - 1] - c[a[0] - 1] == a[2]):
            score += a[3]
    saidai = max(saidai, score)

print(saidai)

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)
ans=0
 
L=[i+1 for i in range(m)]
for l in itertools.combinations_with_replacement(L, n):
#for l in itertools.product(L, repeat=n):
    s=0
    for j in range(q):
        if int(l[B[j]-1])-int(l[A[j]-1])==C[j]:
            s+=D[j]
    ans=max(ans,s)
    if ans==sum(D):
        print(ans)
        exit()
print(ans)

Submission status: Accepted

Solution code:
import itertools
 
N, M, Q = map(int, input().split())
 
int_tuple_list = list()
for i in range(Q):
    int_tuple_list.append(tuple(map(int, input().split())))
 
m_list = [i for i in range(1, M + 1)]
# print(m_list)
all_sequence_list = list()
score_list = list()
for sequence in itertools.combinations_with_replacement(m_list, N):
    # print(sequence)
    score_tmp = 0
    for ai, bi, ci, di in int_tuple_list:
        if ci == sequence[bi - 1] - sequence[ai - 1]:
            score_tmp += di
 
    # print(score_tmp)
    score_list.append(score_tmp)
 
print(max(score_list))

Submission status: Accepted

Solution code:
import sys
import itertools


sys.setrecursionlimit(10 ** 7)

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

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


ans = 0
for lst in itertools.combinations_with_replacement(range(1, M + 1), N):
    s = 0
    for a, b, c, d in ABCD:
        if (lst[b - 1] - lst[a - 1]) == c:
            s += d

    ans = max(ans, s)

print(ans)

Submission status: Accepted

Solution code:
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
import itertools

N, M, Q = MAP()
a, b, c, d = [], [], [], []
for _ in range(Q):
    ai, bi, ci, di = MAP()
    a.append(ai-1); b.append(bi-1); c.append(ci); d.append(di)


def solve(lst):
    ans = 0
    for i in range(Q):
        if lst[b[i]] - lst[a[i]] == c[i]:
            ans += d[i]
    return ans

ans = 0
for A in itertools.combinations_with_replacement(range(1, M+1), N):
    ans = max(ans, solve(A))

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from math import gcd
import time
import sys
from collections import Counter
import itertools
import math
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
start = time.time()
# N = list(map(int, input()))[::-1]
# N = int(input())
N, M, Q = map(int, input().split())
big = 0
s = 2**N
l = []

moto = list(range(1, Q+1))

for i in range(Q):
    l.append(list(map(int, input().split())))

A = []
for i in range(N):
    AA = []
    if A:
        for k in A:
            for j in range(1, M+1):
                if k[-1] <= j:
                    AA.append(k+[j])
        A = AA
    else:
        for j in range(1, M+1):
            A.append([j])

for i in A:
    wa = 0
    for j in l:
        if (i[j[1]-1]-i[j[0]-1]) == j[2]:
            wa += j[3]

    if big < wa:
        big = wa
print(big)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement


def main():
    N, M, Q = list(map(int, input().split(' ')))
    constraint_list = list()
    for _ in range(Q):
        constraint_list.append(list(map(int, input().split(' '))))
    ans = 0
    for A in combinations_with_replacement(range(1, M + 1), N):
        score = 0
        for constraint in constraint_list:
            a, b, c, d = constraint
            if A[b - 1] - A[a - 1] == c:
                score += d
        ans = max([ans, score])
    print(ans)


if __name__ == '__main__':
    main()

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

    import itertools
    for b in itertools.combinations_with_replacement([i for i in range(1,m+1)],n):
        cnt=0
        for v in a:
            if b[v[1]-1]-b[v[0]-1]==v[2]:
                cnt+=v[3]
        ans=max(ans,cnt)

    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:
from collections import deque

def main():
    nmq = list(map(int, input().split()))
    abcd = [None]*50
    for i in range(nmq[2]):
        abcd[i] = list(map(int, input().split()))
    
    ma = 0

    qset = bf([1], nmq[0], nmq[1], [])

    for q in qset:
        score = 0
        for j in range(nmq[2]):
            if q[abcd[j][1]-1] - q[abcd[j][0]-1] == abcd[j][2]:
                score += abcd[j][3]
        if score > ma:
            ma = score

    print(ma)

    
def bf(now, n, m, stock):
    if len(now) == n:
        stock.append(now)
        return now
    for i in range(now[-1], m+1):
        aa = list(now)
        aa.append(i)
        re = bf(aa, n, m, stock)
    return stock
    



if __name__ == '__main__':
    main()