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 numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    N,M,Q = map(int, input().split())
    pair = []
    for i in range(Q):
        pair += list(map(int, input().split())),

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

    ans = 0
    A = [1]*N
    i = N-1
    while True:
        ans = max(ans, score(A))
        while i >= 0 and A[i] == M:
            i -= 1
        if i < 0:
            break
        A[i] += 1
        j = i
        while i <= N-1:
            A[i] = A[j]
            i += 1
        i = N-1
        if A == [M]*N:
            break
        
    print(ans)
main()

Submission status: Accepted

Solution code:
import itertools
n,m,q=map(int,input().split())
array=[list(map(int,input().split())) for _ in range(q)]
a=list(range(1,m+1))
A=[]
for i in itertools.combinations_with_replacement(a,n):
  A.append(list(i))
ans=[0]
for j in range(len(A)):
  AA=A[j]
  count=0
  for i in range(q):
    if AA[array[i][1]-1]-AA[array[i][0]-1]==array[i][2]:
      count+=array[i][3]
    else:
      pass
  ans.append(count)
print(max(ans))

Submission status: Accepted

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

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

# Aの重複組み合わせ結果配列のリスト
A_list = list(itertools.combinations_with_replacement(range(1, M+1), N))
ans = 0
for A in A_list:
  score = 0
  for a, b, c, d in abcd:    
    if A[b-1] - A[a-1] == c:
      score += d
  ans = max(ans, score)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
n, m, q = map(int, input().split())
list_ABCD = [ list(map(int,input().split(" "))) for _ in range(q)]
list_N = [i for i in range(1, m+1)]
ans = 0

for l in combinations_with_replacement(list_N, n):
    score = 0
    for a, b, c, d in list_ABCD:
        if l[b-1] - l[a-1] == c:
            score += d
    ans = max(ans, score)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


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


N, M, Q = 0, 0, 0
A, B, C, D = [0], [0], [0], [0]
ans = 0

def dfs(i, l):
    global ans, N, M, Q, A, B, C, D
    if i >= N:
        tmp = 0
        for j in range(Q):
            if l[B[j]] - l[A[j]] == C[j]:
                tmp += D[j]
        ans = max(ans, tmp)
        return

    for j in range(1, M + 1):
        if l:
            if j >= l[-1]:
                l.append(j)
                dfs(i + 1, l)
                l.pop()
        else:
            l.append(j)
            dfs(i + 1, l)
            l.pop()


def solve():
    global ans, N, M, Q, A, B, C, D
    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

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


def main():
    solve()


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc165/tasks/abc165_c

from itertools import combinations_with_replacement

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

res = []
for A in combinations_with_replacement(range(1,M+1), N):
    score = 0
    for i in range(Q):
        a,b,c,d = data[i]
        if A[b-1] - A[a-1] == c:
            score += d
    res.append(score)

print(max(res))

Submission status: Accepted

Solution code:
def II(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
from itertools import combinations_with_replacement
N,M,Q=MI()
A=[]
B=[]
C=[]
D=[]
ans=0
for i in range(Q):
  a,b,c,d=MI()
  a-=1
  b-=1
  A.append(a)
  B.append(b)
  C.append(c)
  D.append(d)
#print(A,B,C,D)
Num=list(range(1,M+1))
#print(Num)
#print(list(combinations(Num,N)))
for j in list(combinations_with_replacement(Num,N)):
  tmp=0
  for i in range(Q):
    if j[B[i]]-j[A[i]]==C[i]:
      tmp+=D[i]
  ans=max(ans,tmp)  
print(ans)

Submission status: Accepted

Solution code:
import itertools
N, M, Q = map(int,input().split())
ans = 0
A = []
B = []
C = []
D = []
for _ in range(Q):
    a, b, c, d = map(int,input().split())
    A.append(a-1)
    B.append(b-1)
    C.append(c)
    D.append(d)

ans = 0
for seq in itertools.combinations_with_replacement(range(M),N):
    tmp = 0
    for i in range(Q):
        if seq[B[i]] - seq[A[i]] == C[i]:
            tmp += D[i]
    ans = max(ans,tmp)

print(ans)

Submission status: Accepted

Solution code:
(N,M,Q) = map(int,input().split())
Qs = []
for i in range(Q):
    Qs.append(list(map(int,input().split())))
A = [1]*N
score = 0
while(1):
    if A[0]>M:
        break
    current_score = 0
    for i in range(Q):
        if A[Qs[i][1]-1]-A[Qs[i][0]-1] == Qs[i][2]:
            current_score += Qs[i][3]
    score = max(score,current_score)
    for i in range(1,N):
        if A[i]== M:
            A[i-1] += 1
            for j in range(i,N):
                A[j] = A[i-1]
            break
        if i == N-1:
            A[N-1] += 1
print(score)

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
a = [0 for _ in range(Q)]
b = [0 for _ in range(Q)]
c = [0 for _ in range(Q)]
d = [0 for _ in range(Q)]
for k in range(Q):
  a[k], b[k], c[k], d[k] = map(int, input().split())
A = [1 for _ in range(N)]

def point(A):
  p = 0
  for ai, bi, ci, di in zip(a, b, c, d):
    if A[bi-1] - A[ai-1] == ci:
      p += di
  return p

def next(A):
  k = 1
  while k < N+1:
    if A[-k] < M:
      A[-k] += 1
      return A
      break
    else:
      for j in range(1, k+1):
        A[-j] = A[-k-1] + 1
      k += 1

ans = point([M for _ in range(N)])
while A[0] < M:
  ans = max(ans, point(A))
  A = next(A)
print(ans)

Submission status: Accepted

Solution code:
n, m, q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(q)]
a,b,c,d = [],[],[],[]
for i in range(q):
  a.append(abcd[i][0])
  b.append(abcd[i][1])
  c.append(abcd[i][2])
  d.append(abcd[i][3])

def score(A):
  tmp = 0
  for ai, bi, ci, di in zip(a, b, c, d):
      if A[bi] - A[ai] == ci:
          tmp += di
  return tmp

def dfs(A):
  if len(A)==n+1:
    return score(A)
  ans = 0
  for i in range(A[-1],m):
    A.append(i)
    ans = max(ans,dfs(A))
    A.pop()
  return ans

print(dfs([0]))

Submission status: Accepted

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

l=[[0]*4 for i in range(q)]

for i in range(q):
    l[i][0],l[i][1],l[i][2],l[i][3]=map(int,input().split())

a=[]
for i in range(1,m+1):
    a.append(i)
arr=list(itertools.combinations_with_replacement(a,n))

mx=0
for mask in range(len(arr)):
    tpl=arr[mask]
    ans=0
    for i in range(q):
        if tpl[l[i][1]-1]-tpl[l[i][0]-1]==l[i][2]:
            ans+=l[i][3]
    mx=max(ans,mx)

print(mx)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations_with_replacement as comb

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

Max = 0

for A in comb(range(1, M + 1), N):
    score = 0
    for j in range(Q):
        if (A[b[j] - 1] - A[a[j] - 1]) == c[j]:
            score += d[j]

    Max = max(Max, score)

print(Max)

Submission status: Accepted

Solution code:
  
def dfs(A):
    if len(A) == n+1:
        global ans
        total = 0
        for i in range(q):
            if A[b[i]]-A[a[i]] == c[i]:
                total += d[i]
        if total > ans:
            ans = total
        return
    num = A[-1]
    while num <= m:
        dfs(A[:]+[num])
        num += 1
    
                

if __name__ == "__main__":
    n, m, q = map(int, input().split())
    a, b, c, d = [None]*q, [None]*q, [None]*q, [None]*q
    for i in range(q):
        a[i], b[i], c[i], d[i] = map(int, input().split())
    ans = 0
    dfs([1])
    print(ans)

Submission status: Accepted

Solution code:
#n=int(input())
n,m,q=map(int,input().split())
al=[0]*q
bl=[0]*q
cl=[0]*q
dl=[0]*q
for i in range(q):
    al[i],bl[i],cl[i],dl[i]=map(int,input().split())

def score(A):
    res=0
    for ai,bi,ci,di in zip(al,bl,cl,dl):
        if A[bi-1]-A[ai-1]==ci:
            res+=di
    return res
scorelist=[]
def dfs(A):
    global scorelist
    lastone=A[-1] if len(A)>0 else 1
    if len(A)==n:
        scorelist.append(score(A))
        return 
    for v in range(lastone,m+1):
        A.append(v)
        dfs(A)
        A.pop()

dfs([])
print(max(scorelist))

Submission status: Accepted

Solution code:
n,m,q = map(int,input().split())
l = []
def dfs(a):
    if len(a)==n: l.append(a)
    else:
        for i in range(a[-1],m+1):
            dfs(a+[i])
for i in range(m):
    dfs([i+1])
Query = [list(map(int,input().split())) for _ in range(q)]
ans = 0
for li in l:
    tmp = 0
    for a,b,c,d in Query:
        if li[b-1]-li[a-1]==c:
            tmp += d
    ans = max(ans,tmp)
print(ans)

Submission status: Accepted

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

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

ary = [1 for _ in range(N)]
ans = 0
while True:
  #print(ary)
  pt = 0
  for j in range(Q):
    rq = Rq[j]
    if ary[rq[1]-1]-ary[rq[0]-1] == rq[2]:
      pt += rq[3]
  ans = max(ans,pt)
  
  if ary[0] == M:
    break
  
  #次の配列へ
  for i in range(-1, -N-1, -1):
    if ary[i] < M:
      ary[i] += 1
      tmp = ary[i]
      for l in range(i+1, 0):
        ary[l] = tmp
      break
      
print(ans)

Submission status: Accepted

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

abcd=[]
for i in range(Q):
  abcd.append(list(map(int,input().split())))
  abcd[i][0]-=1
  abcd[i][1]-=1

  
def calcScore(target):
  score=0
  for i in range(Q):
    if target[abcd[i][1]]-target[abcd[i][0]]==abcd[i][2]:
      score+=abcd[i][3]
  return score

def makeTarget():
  list=[1]*N
  list[-1]=0
  while True:
    list[-1]+=1
    for i in range(len(list)):
      if list[-i-1]>M:
        if len(list)==i+1:return
        list[-i-2]+=1
        list[-i-1]=0
    for i in range(len(list)-1):
      if list[i]>list[i+1]:list[i+1]=list[i]
    yield list.copy()

ans=0
for i in makeTarget():
  ans=max(ans,calcScore(i))
print(ans)

Submission status: Accepted

Solution code:
import itertools 
N, M, Q = map(int, input().split())
li = [list(map(int, input().split())) for _ in range(Q)]
ans= 0
AA = [i for i in range(1, M+1)]
A = []
for i in sorted(list(itertools.combinations_with_replacement(AA, N))):
    A.append(i)

for i in A:
    result = 0
    for j in range(Q):
        if i[li[j][1]-1]-i[li[j][0]-1] == li[j][2]:
            result += li[j][3]
    ans = max(ans, result)

print(ans)

Submission status: Accepted

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

ans = 0
for c in combinations(range(N+M-1), N):
    x = sorted(list(c))
    ans_new = 0
    for i in range(Q):
        if x[A[i][1]-1] - A[i][1] - x[A[i][0]-1] + A[i][0] == A[i][2]:
            ans_new += A[i][3]
    if ans_new > ans:
        ans = ans_new
print(ans)

Submission status: Accepted

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

ans = 0
for v in combinations_with_replacement(range(1, m+1), n):
    cnt = 0
    for i in range(q):
        if v[s_l[i][1] - 1] - v[s_l[i][0] - 1] == s_l[i][2]:
            cnt += s_l[i][3]
    ans = max(ans, cnt)

print(ans)

Submission status: Accepted

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

A = []
for v in combinations_with_replacement(range(1,m+1), n):
    A.append(v)

ans = 0
for a in A:
    cnt = 0
    for i in range(q):
        if a[s_l[i][1] - 1] - a[s_l[i][0] - 1] == s_l[i][2]:
            cnt += s_l[i][3]
    ans = max(ans, cnt)

print(ans)

Submission status: Accepted

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

ans = 0
for iter in itertools.combinations_with_replacement(range(1,m+1),n):
    result = 0
    for i in range(q):
        a,b,c,d = abcd[i][0],abcd[i][1],abcd[i][2],abcd[i][3]
        if iter[b-1] - iter[a-1] == c:
            result += d
    ans = max(ans, result)

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

abcd_list = []
for q in range(Q):
    abcd_list.append(list(map(int, input().split())))

#print(abcd_list)
list_tmp = []
for i in range(1, M + 1):
    list_tmp.append(i)

comb_A = list(itertools.combinations_with_replacement(list_tmp, N))


max_score = 0
for A in comb_A:
    tmp_score = 0
    for q in range(Q):
        A_a = A[abcd_list[q][0] - 1]
        A_b = A[abcd_list[q][1] - 1]

        if(A_b - A_a == abcd_list[q][2]):
            tmp_score += abcd_list[q][3]
        
    max_score = max(max_score, tmp_score)

print(max_score)

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

# スコア計算
def score(A):
    tmp = 0
    for ai, bi, ci, di in zip(a, b, c, d):
        if A[bi] - A[ai] == ci:
            tmp += di
    return tmp

# DFS
def dfs(A):
    if len(A) == N:
        return score(A) # 数列 A のスコアを返す
    res = 0
    prev_last = A[-1] if len(A) > 0 else 0
    for v in range(prev_last, M):
        A.append(v)
        res = max(res, dfs(A)) # 再帰呼出しながら、スコア最大値も更新
        A.pop()
    return res

# 求める
print(dfs([]))

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

n, m, q = rm()
li = [rl() for _ in range(q)]
max_ = 0
for A in list(itertools.combinations_with_replacement(list(range(1, m+1)), n)):
    score = 0
    for abcd in li:
        a, b, c, d = abcd
        a -= 1
        b -= 1
        if A[b] - A[a] == c:
            score += d
    else:
        max_ = max(score, max_)
print(max_)

Submission status: Accepted

Solution code:
def mi(): return map(int,input().split())
def lmi(): return list(map(int,input().split()))
def ii(): return int(input())
def isp(): return input().split()

from itertools import combinations_with_replacement
n,m,q=mi()
ll=[i for i in range(1,m+1)]

input_list=[]
for i in range(q):
  abcd=lmi()
  input_list.append(abcd)

ans=0
la=list(combinations_with_replacement(ll,n))
for i in la:
  suma=0
  #print(i)
  for j in input_list:
    a=j[0]
    b=j[1]
    c=j[2]
    d=j[3]
    if (i[b-1]-i[a-1])==c:
      suma+=d
      #print(suma)
  ans=max(ans,suma)
  
print(ans)

Submission status: Accepted

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

AA = [[1]*n]

while True:
    for i in reversed(range(n)):
        if AA[-1][i] != m:
            break
    else:
        break
    tmp = copy.deepcopy(AA[-1])
    tmp[i:] = [tmp[i]+1]*(n-i)
    AA.append(tmp)

ans = 0
for i in range(len(AA)):
    pt = 0
    for j in range(q):
        if AA[i][b[j]-1] - AA[i][a[j]-1] == c[j]:
            pt = pt + d[j]
    ans = max(ans,pt)
    
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import copy

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

for i in range(Q):
    xs = [int(_) for _ in input().split()]
    a[i] = xs[0] - 1
    b[i] = xs[1] - 1
    c[i] = xs[2]
    d[i] = xs[3]


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


max_score = -1


def dfs(A):
    if len(A) == N:
        global max_score
        max_score = max(calc_score(A), max_score)
    else:
        if len(A) == 0:
            A.append(1)
        else:
            A.append(A[-1])
        while (A[-1] <= M):
            dfs(copy.deepcopy(A))
            A[-1] += 1


dfs([])
print(max_score)

Submission status: Accepted

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

a_opt = []
for ni in range(n):
    a_opt_next = []
    if len(a_opt) == 0:
        for mi in range(1, m + 1):
            a_next = [mi]
            a_opt_next.append(a_next)
    else:
        for a in a_opt:
            for mi in range(a[-1], m + 1):
                a_next = a + [mi]
                a_opt_next.append(a_next)
    a_opt = a_opt_next[:]

ans = 0
for a in a_opt:
    sumd = 0
    for num_set in num_sets:
        if a[num_set[1] - 1] - a[num_set[0] - 1] == num_set[2]:
            sumd += num_set[3]
    ans = max(ans, sumd)

print(ans)

Submission status: Accepted

Solution code:
#cited from maspy
import itertools
import numpy as np

N, M, Q = map(int, input().split())
A = np.array(list(itertools.combinations_with_replacement(range(1, M + 1), N)))
n = len(A)
score = np.zeros(n, np.int32)
m = [list(map(int, input().split())) for i in range(Q)]
for a, b, c, d in m:
    cond = A[:, b - 1] - A[:, a - 1] == c
    score += d * cond
print(score.max())

Submission status: Accepted

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

def make_group(now, n, i):
    if n == 0:
        groups.append(now)
    else:
        for j in range(i, M+1): 
            make_group(now+[j], n-1, j)

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

groups = []
now = []
make_group(now, N, 1)

ans = 0
for group in groups:
    tmp = 0
    for a, b, c, d in zip(A, B, C, D):
        if group[b-1]-group[a-1] == c:
            tmp += d
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
n,m,q = map(int,input().split())
pairs = []
def makelen(a):
    if len(a) == n:
        pairs.append(a)
    else:
        for i in range(a[-1],m+1):
            makelen(a + [i])
for i in range(m):
    makelen([i+1])
Query = [list(map(int,input().split())) for _ in range(q)]
ans = 0
for pair in pairs:
    tmpans = 0
    for a,b,c,d in Query:
        if pair[b-1] - pair[a-1] == c:
            tmpans += d
    ans = max(tmpans,ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n, m, q = map(int, input().split())
si, res = [1] + [0 for i in range(55)], 0
a, b, c, d = [0 for i in range(55)], [0 for i in range(55)], [0 for i in range(55)], [0 for i in range(55)]
for i in range(1, q+1): a[i], b[i], c[i], d[i] = map(int, input().split())

def solve(x: int):
    global res
    if x == n + 1: res = max(res, sum([d[i] for i in range(1, q+1) if si[b[i]] - si[a[i]] == c[i]]))
    else:
        for i in range(si[x-1], m + 1): si[x] = i; solve(x+1)
solve(1); print(res)

Submission status: Accepted

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

# N = [4, 6, 10]
# Q = [[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]]

from itertools import combinations_with_replacement as comb_rplc

C = 0
for seq in comb_rplc(range(1, N[1]+1), N[0]):
    S = 0
    for i in range(N[2]):
        if seq[Q[i][1]-1]-seq[Q[i][0]-1] == Q[i][2]:
            S += Q[i][3]
    if S > C:
        C = S
print(C)

Submission status: Accepted

Solution code:
import itertools
N, M, Q = map(int, input().split())
max = 0
s = ''
for i in range(M):
    s += str(i)
l = list(itertools.combinations_with_replacement(s, N))
m = [list(map(int, input().split())) for i in range(Q)]
for x in l:
    count = 0
    for y in m:
        if int(x[y[1] - 1]) - int(x[y[0] - 1]) == y[2]:
            count += y[3]
    if count > max:
        max = count
print(max)

Submission status: Accepted

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

for A in H(list(range(1, M+1)), N):
    acc = 0
    for j in range(Q):
        a, b, c, d = query[j]
        if A[b - 1] - A[a - 1] == c:
            acc += d
    ans = max(ans, acc)
print(ans)

Submission status: Accepted

Solution code:
def dfs(A):
    if len(A) == n+1:
        p = 0
        global ans
        for i in range(q):
            if A[b[i]]-A[a[i]] == c[i]:
                p += d[i]
        if p > ans:
            ans = p
        return
    num = A[-1]
    while num <= m:
        dfs(A[:]+[num])
        num += 1


if __name__ == "__main__":
    n, m, q = map(int, input().split())
    a, b, c, d = [None]*q, [None]*q, [None]*q, [None]*q
    for i in range(q):
        a[i], b[i], c[i], d[i] = map(int, input().split())
    ans = 0
    dfs([1])
    print(ans)

Submission status: Accepted

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

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

ans =0
for A in cwr(range(1,m+1),n):
    ans = max(ans, calscore(A))
print(ans)

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

n,m,q=map(int,input().split())
A=list(range(1,m+1))
s=(list(combinations_with_replacement(A,n)))
a=[0]*q
b=[0]*q
c=[0]*q
d=[0]*q

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

for i in s:
    total=0
    for j in range(q):
        if i[b[j]-1]-i[a[j]-1]==c[j]:
            total+=d[j]
    ans=max(ans,total)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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


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


ans = 0
for A in combinations_with_replacement([i for i in range(M)], N):
    ans = max(ans, cal_score(A))
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as cwr

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

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

ans = 0
for A in cwr([i for i in range(1, M+1)], N):
  ans = max(ans, calc_score(A))

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

com_list = list(itertools.combinations_with_replacement(range(M), N))
ans = 0
for com in com_list:
    tmp = 0
    for abcd in abcd_list:
        if (com[abcd[1]-1] - com[abcd[0]-1]) == abcd[2]:
            tmp += abcd[3]
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
#create date: 2020-06-30 14:42

import sys
stdin = sys.stdin
from itertools import combinations_with_replacement

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n, m, q = na()
    matrix = list()
    for i in range(q):
        matrix.append(na())
    l = list(combinations_with_replacement(range(1, m+1), n))
    ans = 0
    for li in l:
        res = 0
        for q in matrix:
            a, b, c, d = q
            if li[b-1] - li[a-1] == c:
                res += d
        ans = max(ans, res)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
    return int(input())

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



def solve():
    n, m, q = rl()
    Q = []
    for i in range(q):
        Q.append(rl())

    ways = [[i] for i in range(1, m + 1)]
    for i in range(n - 1):
        new_ways = []
        for way in ways:
            new_way = list(way)
            for j in range(way[-1], m + 1):
                new_ways.append(new_way + [j])
        ways = new_ways

    best = 0
    for way in ways:
        tot = 0
        for a, b, c, d in Q:
            if way[b - 1] - way[a - 1] == c:
                tot += d
        best = max(best, tot)

    print (best)







mode = 's'

if mode == 'T':
    t = ri()
    for i in range(t):
        solve()
else:
    solve()

Submission status: Accepted

Solution code:
import itertools

N, M, Q = map(int, input().split())
q = [list(map(int, input().split())) for _ in range(Q)]
a = [0] * N
max_score = 0
for v in itertools.combinations(range(N + M - 1), N):
    tmp_score = 0
    for n in range(N):
        a[n] = v[n] + 1 - n
    for query in q:
        if (a[query[1] - 1] - a[query[0] - 1]) == query[2]:
            tmp_score += query[3]
    if max_score < tmp_score:
        max_score = tmp_score
print(max_score)

Submission status: Accepted

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

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


ma = 0
for i in k:
    su = 0
    for n in s:
        if i[n[1]-1] - i[n[0]-1] == n[2]:
            su += n[3]
    ma = max(ma,su)

print(ma)

Submission status: Accepted

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

(n, m, q), *r = [[*map(int, t.split())] for t in open(0)]
ans = 0
for i in list(itertools.combinations_with_replacement(range(1, m + 1), n)):
    sub = 0
    for a, b, c, d in r:
        sub += d * (i[b - 1] - i[a - 1] == c)
    ans = max(ans, sub)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N, M, Q = MI()
    D = [[] for _ in range(Q)]
    for i in range(Q):
        a, b, c, d = MI()
        a -= 1
        b -= 1
        D[i] = [a, b, c, d]

    ans = 0
    for K in comb_w(range(1, M+1), N):
        score = 0
        for q in range(Q):
            a, b, c, d = D[q]
            if K[b] - K[a] == c:
                score = score + d
        ans = max(ans, score)

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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

def calc(li):
    score = 0
    for a, b, c, d in l:
        if li[b-1]-li[a-1] == c:
            score += d
    return score

que = deque([[i] for i in range(1, M+1)])
ans = 0

while que:
    li = que.popleft()
    if len(li) == N:
        score = calc(li)
        ans = max(ans, score)
    else:
        for i in range(li[-1],M+1):
            next = li + [i]
            que.append(next)
    #print(que)

print(ans)