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 = [list(map(int, input().split())) for i in range(Q)]
matrix = list(itertools.combinations_with_replacement([i for i in range(M)], N))
ans = [0 for i in range(len(matrix))]

for i in range(len(matrix)):
  for j in range(Q):
    if matrix[i][A[j][1]-1] - matrix[i][A[j][0]-1] == A[j][2]:
      ans[i] += A[j][3]
  

print(max(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)]

num = []

for i in range(1, m + 1):
    num.append(i)


ans = 0


for A in list(itertools.combinations_with_replacement(num, n)):
    p = 0
    for abcdi in abcd:
        if A[abcdi[1] - 1] - A[abcdi[0] - 1] == abcdi[2]:
            p += abcdi[3]
    
    if p > ans:
        ans = p

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

ans = 0

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

import itertools
for A in itertools.combinations_with_replacement(l, N):
    # flag = False
    point = 0
    # for i in range(1,N):
    #     if A[i] > A[i-1]:
    #         flag = True
    #         break
    # if flag:
    #     continue

    # print(A)
    for k in range(Q):
        a = abcd[k][0]
        b = abcd[k][1]
        c = abcd[k][2]
        d = abcd[k][3]
        if A[b - 1] - A[a - 1] == c:
            point += d
        if point > ans:
            ans = point

# A = [1 for i in range(N)]
#
# for i in range(N-1,-1,-1):
#     for j in range(M):
#         A[i] += 1
#         print(A)
#         point = 0
#         for k in range(Q):
#             a = abcd[k][0]
#             b = abcd[k][1]
#             c = abcd[k][2]
#             d = abcd[k][3]
#             if A[b-1]-A[a-1] == c:
#                 point += d
#         if point > ans:
#             ans = point
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)]
ans=0
A=[i for i in range(1,M+1)]
#print(A)

T=[[i] for i in range(1,M+1)]
for i in range(N-1):
    newT=[]
    for j in range(len(T)):
        t=T[j]
        num=T[j][-1]
        while num<=M:
            newT.append(t+[num])
            num+=1
    T=newT
#print(T)

for x in range(len(T)):
    points=0
    #print(T[x])
    for q in range(Q):
        a=ABCD[q][0]
        b=ABCD[q][1]
        if T[x][b-1]-T[x][a-1]==ABCD[q][2]:
            points+=ABCD[q][3]
    ans=max(ans,points)

print(ans)

Submission status: Accepted

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

for pair in itertools.combinations_with_replacement(list(range(1,m+1)),n):
    res=0
    for i in range(q):
        if(pair[data[i][1]-1]-pair[data[i][0]-1]==data[i][2]):
            res+=data[i][3]
    ans=max(ans,res)

print(ans)

Submission status: Accepted

Solution code:
import sys

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

a = [0 for i in range(q)]
b = [0 for i in range(q)]
c = [0 for i in range(q)]
d = [0 for i in range(q)]

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

x = [0 for i in range(n)]

best = -1

def search(min_elem, pos):
	global best
	global a
	global b
	global c
	global d
	if (pos == n):
		score = 0		
		for i in range(q):			
			if x[b[i] - 1] - x[a[i] - 1] == c[i]:
				score += d[i]
		best = max(best, score)

	else: 
		for i in range(min_elem, m + 1):
			x[pos] = i
			search(i, pos + 1)

search(1, 0)
print(best)

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 165: C (2020/05/02)
import itertools
N, M, Q = map(int, input().split())
ans = 0
a = [0 for i in range(Q)]
b = [0 for i in range(Q)]
c = [0 for i in range(Q)]
d = [0 for i in range(Q)]
for j in range(Q):
    a[j], b[j], c[j], d[j] = map(int, input().split())
seq = [i+1 for i in range(M)]
As = list(itertools.combinations_with_replacement(seq, N))
ans = 0
for j in range(len(As)):
    A = As[j]
    max = 0
    for i in range(Q):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            max = max + d[i]
    if ans < max:
        ans = max
print(ans)

Submission status: Accepted

Solution code:

def next_A(A):
    rev_A = list(reversed(A))
    max_num = M
    if rev_A[0] < M:
        rev_A[0] = rev_A[0] + 1
        return list(reversed(rev_A))
    
    for i in range(N):
        if rev_A[i] < max_num:
            rev_A[i] = rev_A[i] + 1
            for j in reversed(range(i)):
                rev_A[j] = rev_A[j+1]
            return list(reversed(rev_A))
        max_num = rev_A[i]
    return [-1]



def make_A():
    A = []
    for i in range(N):
        A.append(1)
    return A

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




#A = []
#len(A) == N
#A[b[i]] - A[a[i]] == c[i]

N,M,Q = (-1,-1,-1)
a = []
b = []
c = []
d = []


N,M,Q = map(int,input().split())
for i 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)
    
A = make_A()
ans = 0
while(-1 not in A):
    #print(A)
    ans = max(solve(A),ans)
    A = next_A(A)
print(ans)

Submission status: Accepted

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def gen(N, M):
    if N == 0:
        for i in range(1, M+1):
            yield [i]
    else:
        prefixes = gen(N-1, M)
        for prefix in prefixes:
            for end in range(prefix[-1], M+1):
                prefix.append(end)
                yield prefix
                prefix.pop()
    

def solve():
    N, M, Q = read_ints()
    a, b, c, d = [], [], [], []
    for _ in range(Q):
        x, y, z, w = read_ints()
        a.append(x)
        b.append(y)
        c.append(z)
        d.append(w)
    max_score = 0
    for A in gen(N, M):
        total_score = 0
        for i in range(Q):
            if A[b[i]-1]-A[a[i]-1] == c[i]:
                total_score += d[i]
        max_score = max(max_score, total_score)
    return max_score


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
import itertools

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

for i in range(Q):
  li.append(list(map(int,input().split())))
li.sort(key = lambda x:x[3])
num = [i for i in range(1,M+1)] 
l = list(itertools.combinations_with_replacement(num, N))
max_sum=-1
for i in range(len(l)):
  s = 0
  for j in range(Q):
    if l[i][li[j][1]-1] -  l[i][li[j][0]-1] == li[j][2]:
      s+= li[j][3]
      
  max_sum = max(max_sum,s)
print(max_sum)

Submission status: Accepted

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

def dfs(seen, v, M, N, Q, a, b, c, d, mx):
    seen[v] = True
    if len(list(v)) == N:
        p = 0
        for i in range(Q):
            if v[b[i]-1] - v[a[i]-1] == c[i]:
                p += d[i]
        if mx < p:
            mx = p
        return mx
    for x in [list(v) + [i] for i in range(v[-1],M+1)]:
        x = tuple(x)
        if not x in seen.keys():
            seen[x] = False
        if seen[x] == True:
            continue
        mx = max(mx, dfs(seen, x, M, N, Q, a, b, c, d, mx))
    return mx

def solve(N: int, M: int, Q: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
    seen = {}
    mx = 0
    c = dfs(seen, (1,), M, N, Q, a, b, c, d, mx)
    print(c)
    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:
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()))

lun = [0]*N
l = []

def make(n):
    if len(n) > N:
        return 0
    if int(n) > 3234566667:
        return 0
    else:

        p = []
        for i in range(int(n[-1]),M):
            p.append(str(i))

        lun.append(n)
        for i in p:
            lun.append(n)
            if len(n) == N:
                l.append(n)
            make(n+i)
        return 0
for i in range(M):
    make(str(i))

l = list(set(l))

nax = 0
for x in l:
    score = 0
    for i in range(Q):
        if int(x[b[i]-1]) - int(x[a[i]-1]) == c[i]:
            score += d[i]
    nax = max(nax,score)

print(nax)

Submission status: Accepted

Solution code:
# from math import factorial,sqrt,ceil,gcd
from itertools import permutations,combinations,combinations_with_replacement
# from collections import deque,Counter
# import re
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import networkx as nx
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb

# slist = "abcdefghijklmnopqrstuvwxyz"
N,M,Q = map(int,input().split())
times = Q
abcds = []
for _ in range(times):
    abcds.append(list(map(int,input().split()))) # 行列の場合
AnoMoto = list(range(1,M+1))
# print(AnoMoto)
# lenA = len(arrA)
ans = 0
for lisA in combinations_with_replacement(AnoMoto,N):
    # print(lisA)
    num = 0
    for abcd in abcds:
        a,b,c,d = abcd
        if lisA[b-1] - lisA[a-1] == c:
            num += d
        ans = max(ans,num)

print(ans)
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))

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, gcd
from itertools import combinations_with_replacement, accumulate, permutations, combinations, product, groupby
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()
graph = [[] for _ in range(N)]
abcd = [LIST() for _ in range(Q)]
ans = 0

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

Submission status: Accepted

Solution code:
import collections
from collections import defaultdict
import math
import numpy as np
import re
import itertools


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

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

ans = 0

for i in itertools.combinations_with_replacement(range(1,m+1), r=n):
    #if i[0] > i[1] or i[0] > i[2] or i[1] > i[2]:
    #    continue
    tmp_ans = 0
    for j in s:    
        #print(i[j[0]-1],i[j[1]-1],j)  
        if i[j[1]-1]-i[j[0]-1] == j[2]:
            tmp_ans += j[3]
    ans = max(ans,tmp_ans)

print(ans)

Submission status: Accepted

Solution code:
N, M, Q = [int(_) for _ in input().split()]
ABCD = [[int(_) for _ in input().split()] for _ in range(Q)]
cand = [[i] for i in list(range(1, M + 1))]
for i in range(N - 1):
    candn = []
    for l in cand:
        j = l[-1]
        candn += [l + [k] for k in range(j, M + 1)]
    cand = candn
ans = 0
for l in cand:
    x = 0
    for a, b, c, d in ABCD:
        if l[b - 1] - l[a - 1] == c:
            x += d
    ans = max([ans, x])
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

def dfs(x, y, z, res):
    if y == n:
        res = max(res, check(x))
        return res
    for i in range(z, m+1):
        res = max(res, dfs(x + [i], y+1, i, res))
    return res

n, m, q = LI()
abcd = [LI() for _ in range(q)]
ans = dfs([1], 0, 1, 0)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

def evaluate(A, matrix):
  total = 0
  for a,b,c,d in matrix:
    if (A[b - 1] - A[a - 1]) == c:
      total += d
  return total

print(max([evaluate(A, matrix) for A in combinations_with_replacement(range(1, M + 1), N)]))

Submission status: Accepted

Solution code:
import itertools

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

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

ans = 0
for c in comb_list:
    ans_tmp = 0
    for l in lit:
        if c[l[1]-1] - c[l[0]-1] == l[2]:
            ans_tmp += l[3]

    if ans < ans_tmp:
        ans = ans_tmp

print(ans)

Submission status: Accepted

Solution code:
import itertools

N, M, Q = map(int, raw_input().split())
data = [None] * Q
for i in range(Q):
    data[i] = map(int, raw_input().split())

def calc_score(data, A):
    score = 0
    for a, b, c, d in data:
        if A[b-1] - A[a-1] == c:
            score += d
    return score

print max(calc_score(data, A) for A in itertools.combinations_with_replacement(range(1, M+1), N))

Submission status: Accepted

Solution code:
import itertools

N,M,Q=list(map(int,input().split()))
s = [list(map(int,input().split())) for i in range(Q)]
int_list=[i for i in range(1,M+1)]
score_list=[]
for v in itertools.combinations_with_replacement(int_list, N):
  score=0
  for list_s in s:
    if v[list_s[1]-1]-v[list_s[0]-1]==list_s[2]:
      score+=list_s[3]
  score_list.append(score)

print(max(score_list))

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

def main():
    n,m,q = (int(x) for x in input().split())
    A = list(combinations_with_replacement(range(1,m+1),n))
    query = [[int(x) for x in input().split()] for _ in range(q)]
    pmax = 0

    for i in A:
        Ai = list(i)
        if Ai != sorted(Ai): continue
        p = 0
        for j in query:
            if Ai[j[1]-1] - Ai[j[0]-1] == j[2]:
                p += j[3]
        pmax = max(p,pmax)

    print(pmax)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))
import itertools
n,m,q = iim()

ans = 0
l = []
for i in range(q):
    l.append(iil())

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

Submission status: Accepted

Solution code:
import math
import itertools

n, m, q = map(int, input().split(" "))
aL = []
_max = 0

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

zLi = itertools.combinations_with_replacement(list(range(m + 1)), n)
for t in zLi:
    if t[0] == 0:
        continue
    _sum = 0
    for a in aL:
        if t[a[1] - 1] - t[a[0] - 1] == a[2]:
            _sum += a[3]
    _max = max(_max, _sum)

print(_max)

Submission status: Accepted

Solution code:
def f(A, i, N, reqs, M, Q):
    if i == N:
        res = 0
        # print(A)
        for i in range(Q):
            a,b,c,d = reqs[i]
            if A[b] - A[a] == c:
                res += d
        # print(res)
        return res
    b = 0
    for n in range(A[i-1],M+1):
        A[i] = n
        b = max(b, f(A,i+1,N,reqs,M,Q))
    return b

def main():
    N,M,Q = [int(_n) for _n in input().split()]
    reqs = []
    for i in range(Q):
        a,b,c,d = [int(_n) for _n in input().split()]
        a-=1
        b-=1
        reqs.append((a,b,c,d))
    print(f([1]*N,1,N,reqs,M,Q))
main()

Submission status: Accepted

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

data=[]

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

l=range(1,m+1)

#h = itertools.combinations_with_replacement(l, 2)
koho = list(itertools.combinations_with_replacement(l, n))

#print(len(koho))

ans=0

for k in koho:
    score=0
    for d in data:
        if(k[d[1]-1]-k[d[0]-1]==d[2]):
            score+=d[3]
    if(score>ans):
        ans=score

print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M,Q=map(int,input().split())
L=[list(map(int, input().split())) for _ in range(Q)]
m=[x for x in range(1, M+1)]
A=list(itertools.combinations_with_replacement(m ,N))
ans=0
for a in A:
    d=0
    for i in range(Q):
        if a[L[i][1]-1]-a[L[i][0]-1]==L[i][2]:
            d+=L[i][3]    
    ans=max(ans,d)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
N, M, Q = map(int, input().split())
a, b, c, d = [], [], [], []
for _ in range(Q):
    ta, tb, tc, td = map(int, input().split())
    ta -= 1
    tb -= 1
    a.append(ta)
    b.append(tb)
    c.append(tc)
    d.append(td)

x = []
def dfs(s):
    if len(s) - s.count("0") == N:
        x.append(s)
        return

    if s[-1] == "0":
        start = 10
    else:
        start = s[-1]
    for i in range(int(start), M+1):
        dfs(s + str(i))
        # x.append(res)

ans = 0
for i in range(1, M+1):
    x = []
    dfs(str(i))
    # print(x)
    for y in x:
        A = []
        for z in y:
            if z == "0":
                A[-1] += z
            else:
                A.append(z)
        A = [int(z) for z in A]
        # print(A)
        score = 0
        for ta, tb, tc, td in zip(a, b, c, d):
            if A[int(tb)] - A[int(ta)] == tc:
                score += td
        ans = max(ans, score)
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

for array in itertools.combinations_with_replacement(range(m), n):
  score = 0
  for r in requirements:
    if array[r[1] - 1] - array[r[0] - 1] == r[2]:
      score += r[3]
  maximum = max(maximum, score)
  
print(maximum)

Submission status: Accepted

Solution code:
import itertools

def p(n, m):
    l = range(1, m+1)
    return list(itertools.combinations_with_replacement(l, n))

def require(n, m, e):
    point = 0
    l = p(n, m)
    for i in list(l):
        tmp = 0
        for a,b,c,d in e:
            if i[b-1] - i[a-1] == c:
                tmp += d
        if tmp > point:
            point = tmp
    print(point)

n,m,q  = [int(i) for i in input().split()]
e = []

for _ in range(q):
    e.append([int(i) for i in input().split()])

require(n,m,e)

Submission status: Accepted

Solution code:
import sys
N,M,Q=map(int,input().split())
nums=[]
for i in range(Q):
  nums.append(list(map(int,input().split())))
ans=0
bit=[1]*N


while True:
  tmp=0
  for num in nums:
    if bit[num[1]-1]-bit[num[0]-1]==num[2]:
      tmp+=num[3]
  if tmp>ans:
    ans=tmp
  n=-1
  while True:
    if (-1)*n>N:
      print(ans)
      sys.exit()
    if bit[n]<M:
      bit[n]+=1
      for j in range(n*(-1)):
        j=(-1)*(j+1)
        bit[j]=bit[n]
      break
    n-=1
print(ans)

Submission status: Accepted

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

#lis = np.array(lis)
#lis = sorted(lis,reverse=True, key=lambda x:x[3])
pool = [0 for _ in range(M)]
for i in range(M):
    pool[i] = i+1
max = 0
for i in itertools.combinations_with_replacement(pool,N):
    #print(i)
    sum = 0
    for j in range(Q):
        if i[lis[j][1]-1] - i[lis[j][0]-1] == lis[j][2]:
            sum += lis[j][3]

    if sum>= max:
        #print(i)
        max = sum


print(max)

Submission status: Accepted

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


def main():
    n, m, q = map(int, input().split())
    ans = 0
    table = itertools.combinations_with_replacement(range(1, m+1), n)
    abcd = [[] for _ in range(q)]
    for i in range(q):
        abcd[i] = list(map(int, input().split()))
    for t in table:
        score = 0
        for i in range(q):
            if(t[abcd[i][1]-1] - t[abcd[i][0]-1] == abcd[i][2]):
                score += abcd[i][3]
        ans = max(score, ans)
    print(ans)


main()

Submission status: Accepted

Solution code:
def calc(l):
    tmp = 0
    #print(l)
    for Q in Qs:
        if l[Q[1] - 1] - l[Q[0] - 1] == Q[2]:
            tmp += Q[3]
    return tmp


def solve(l, d):
    global n
    global ans
    if d == n:
        ans = max(ans, calc(l))
        return
    for i in range(l[-1], m + 1):
        l_ = l + [i]
        solve(l_, d + 1)


n, m, q = map(int, input().split())
Qs = [list(map(int, input().split())) for _ in range(q)]
ans = 0
for i in range(1, m + 1):
    solve([i], 1)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools

n, m, q = map(int, input().split())  # x = 1, y = 2
abcd = list(list(map(int, input().split())) for _ in range(q))

# print(n, m, q, abcd)

combis = list(itertools.combinations_with_replacement(range(1, m + 1), n))
# print(combis)
max_sum = 0
for patt in combis:
    sumv = 0
    for abc in abcd:
        [a, b, c, d] = abc
        if c == (patt[b - 1] - patt[a - 1]):
            sumv += d
    if max_sum < sumv:
        max_sum = sumv

print(max_sum)

Submission status: Accepted

Solution code:
def main():
    n,m,q=map(int,input().split())
    abcd=[]
    for _ in range(q):
        a,b,c,d=map(int,input().split())
        abcd.append((a,b,c,d))
    pmax=0
    aa=[1]*n
    while True:
        p=0
        for a,b,c,d in abcd:
            if aa[b-1]-aa[a-1]==c:
                p+=d
        if p>pmax:
            pmax=p
        for i in range(1,n+1):
            if aa[-i] < m:
                aa[-i]+=1
                while i>1:
                    aa[-i+1]=aa[-i]
                    i-=1
                break
        else:
            print(pmax)
            return
main()

Submission status: Accepted

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

A = list(itertools.combinations_with_replacement(range(1, m + 1), n))
ans = 0

for i in range(len(A)):
    tmp = 0
    for j in range(q):
        if A[i][T[j][1] - 1] - A[i][T[j][0] - 1] == T[j][2]:
            tmp = tmp + T[j][3]
    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
n,m,q=mii()
arr=[]
for i in range(q):
    a,b,c,d=mii()
    arr.append([a,b,c,d])
ans=0
for i in combinations_with_replacement(list(range(1,m+1)),n):
    temp=0
    for j in arr:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            temp+=j[3]
    ans=max(temp,ans)
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys

sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    N, M, Q = map(int, input().split())
    A, B, C, D = [0] * Q, [0] * Q, [0] * Q, [0] * Q
    for i in range(Q):
        A[i], B[i], C[i], D[i] = map(int, input().split())

    ans = 0
    L = [i for i in range(1, M + 1)]
    LL = list(combinations_with_replacement(L,N))
    for i in LL:
        ls = i
        cnt = 0
        for j in range(Q):
            if ls[B[j] - 1] - ls[A[j] - 1] == C[j]:
                cnt += D[j]
        ans = max(ans, cnt)
    print(ans)


resolve()

Submission status: Accepted

Solution code:
n,m,q = map(int, input().split())
res = 0
a = []*n

for i in range(q):
  a.append(list(map(int, input().split())))
for i_1 in range(1,m+1):
  for i_2 in range(i_1,m+1):
    for i_3 in range(i_2,m+1):
      for i_4 in range(i_3,m+1):
        for i_5 in range(i_4,m+1):
          for i_6 in range(i_5,m+1):
            for i_7 in range(i_6,m+1):
              for i_8 in range(i_7,m+1):
                for i_9 in range(i_8,m+1):
                  tmp = 0
                  arr = [1,i_1,i_2,i_3,i_4,i_5,i_6,i_7,i_8,i_9]
                  for i in range(q):
                    if arr[a[i][1]-1] - arr[a[i][0]-1] == a[i][2]:
                      tmp += a[i][3]
                  res = max(res,tmp)
print(res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations, combinations_with_replacement
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from math import gcd

# dを大きい方から取って行きたい
# A1は1として問題ない。
# 数列を仮定して探索すれば良い
N, M, Q = read_ints()
DATA = read_tuple(Q)
A = [1 + x for x in range(M)]


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


ans = 0
for AA in combinations_with_replacement(A, r=N):
    ans = max(ans, ret_score(AA))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools

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

Submission status: Accepted

Solution code:
n,m,q = map(int,input().split())
abcd = [list(map(int,input().split())) for _ in range(q)]
s = [[1]]
for i in range(1,n):
    s_ = []
    for j in s:
        for k in range(j[-1],m+1):
            s_.append(j+[k])
    s = s_
    
ans = 0
for i in s:
    ans_ = 0
    for j in abcd:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            ans_ += j[3]
    ans = max(ans, ans_)

print(ans)