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:
# -*- coding: utf-8 -*-
import sys
import itertools#これは色々使える組み込み関数みたいなやつ
import fractions
import copy
import bisect
import math
import numpy as np
from itertools import combinations_with_replacement
#import math#数学的計算はこれでいける。普通に0.5乗しても計算可能
#w=input()
from operator import itemgetter
from sys import stdin
#input = sys.stdin.readline#こっちの方が入力が早いが使える時に使っていこう
from operator import mul
from functools import reduce
from collections import Counter
#from collections import deque

#input = stdin.readline


j=0
k=0
n=3
r=1
a=[0]*5
b=[]
#n=int(input())
#r=int(input())
#print(M)
#A=int(input())
#B=int(input())
#print(N)
"1行1つの整数を入力を取得し、整数と取得する"


#number_list=list(map(int, input().split(" ")))#数字の時
#print(number_list)
"12 21 332 とか入力する時に使う"
"1行に複数の整数の入力を取得し、整数として扱う"

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
#メモ
for i in number_list:#こっちの方がrage使うより早いらしい
    print(number_list[i-1])#

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''

'''
x=[]
y=[]
for i in range(N):
    x1, y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)
print(x)
print(y)
"複数行に2数値を入力する形式 x座標とy座標を入力するイメージ"
'''

'''
mixlist=[]
for i in range(N):
    a,b=input().split()
    mixlist.append((int(a),b))
print(mixlist)
"複数行にintとstrを複合して入力するやつ，今回はリスト一つで処理している"
'''

'''
#array=[input().split()for i in range(N)]
#print(type(array[0][0]))
#print(array)
"正方行列にstr型の値を入力"
'''

#brray=[list(map(int, input().split(" ")))for i in range(N)]
#print(type(brray[0][0]))
#print(brray)
'''
入力
1 2
4 5
7 8
出力結果
[[1, 2], [4, 5], [7, 8]]
'''
"列数に関して自由度の高いint型の値を入力するタイプの行列"
#以下に別解を記載
#N, M = [int(i) for i in input().split()]
'''
table = [[int(i) for i in input().split()] for m in range(m)]

print(type(N))
print(N)
print(type(M))
print(M)

print(type(table))
print(table)
'''




#s=input()
#a=[int(i) for i in s]
#print(a[0])
#print([a])
#単数値．桁ごとに分割したい．入力と出力は以下の通り
#イメージとして1桁ごとにリストに値を入れているかんじ
#intを取ると文字列分解に使える
'''
入力
1234
出力
1
[[1, 2, 3, 4]]
'''




'''
word_list= input().split(" ")
print(word_list[0])
"連続文字列の入力"
"qw er ty とかの入力に使う"
"入力すると空白で区切ったところでlistの番号が与えられる"
'''



'''
A, B, C=stdin.readline().rstrip().split()#str style 何個でもいけることが多い
print(A)
"リストではなく独立したstr型を入れるなら以下のやり方でOK"
'''


#a= stdin.readline().rstrip()
#print(a.upper())
"aという変数に入っているものを大文字にして出力"


#a,b=map(int, input().split())  #int style 複数数値入力　「A B」みたいなスペース空いた入力のとき

#なんかうまく入力されるけど
#a=[[int(i) for i in 1.strip()]for 1 in sys.stdin]
#a = [[int(c) for c in l.strip()] for l in sys.stdin]]
#print(a)
#複数行の数値を入力して正方行列を作成


##############################################################################################
##############################################################################################
#under this line explains example calculation

'''
コンビネーションの組み合わせの中身を出力する形式
for i in itertools.combinations(brray, 2)
combinationsをpermutationsにすれば順列になる
今回なら(abc133B)
入力
1 2
5 5
-2 8
出力
[[1, 2], [5, 5], [-2, 8]]
もちろん一次元リストでも使えるし
何よりiもリストのように使えるので便利
'''

#nCr combination
'''
def cmb(n,r):
    #When n < r , this function isn't valid
    r= min(n-r,r)
    #print(n,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n-r, -1))
    #flochart mul(n,n-1)=x
    #next     mul(x,n-2)........(n-r+1,n-r)
    #mul read a,b and returns a*b

    under = reduce(mul, range(1, r+1))
    #print(over, under)
    #reduce is applied mul(1,2)=2
    #next   mul(2,3)=6
    #next   mul(6,4)=4.........last(r!,r+1)=r+1!

    return over // under
    #// is integer divide
    #calc example 5C2
    #over=5*4*3
    #under=3*2*1
a = cmb(n, r)
#print(a)
'''

'''
#集計
#example
#a=[2,2,2,3,4,3,1,2,1,3,1,2,1,2,2,1,2,1]
#a=Counter(a)
for i in a.most_common(n):print(i)
#most_common()メソッドは、出現回数が多い要素順にCounterオブジェクトを並び替えます。
#引数にint型の数字nを設定した場合は、出現回数が高い上位ｎ個の要素を返します。
#何も設定しなければ、コンテナ型にあるすべての要素を出現回数の順番に並び替えたタプル型オブジェクトを返します。
#out put
#(2, 8)
 #(1, 6)
#(3, 3)
#(4, 1)
'''


#二部探索(binary search)
#A = [1, 2, 3, 3, 3, 4, 4, 6, 6, 6, 6]
#print(A)
#index = bisect.bisect_left(A, 5) # 7 最も左(前)の挿入箇所が返ってきている
#A.insert(index, 5)
#print(index)
#print(A)
'''
bisect.bisect_left(a, x, lo=0, h=len(a))
引数
a: ソート済みリスト
x: 挿入したい値
lo: 探索範囲の下限
hi: 探索範囲の上限
(lo, hiはスライスと同様の指定方法)
bisect_leftはソートされたリストaに対して順序を保ったままxを挿入できる箇所を探索します。leftが示す通り、aにすでにxが存在している場合は、挿入箇所は既存のxよりも左側になります。また、lo, hiを指定することで探索範囲を絞り込むことも可能です。デフォルトはaの全体が探索対象です。
'''





########################################################################
########################################################################
#b2=a[:]  #1次元のときはコピーはこれで良い
#print(b2)

#a= [[0]*3 for i in range(5)] #2次元配列はこう準備、[[0]*3]*5だとだめ
#b3=copy.deepcopy(a)  #2次元配列はこうコピーする
#print(b3)



input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
'''
講評：検索対象の数列を全て数え上げる発想まではあっていた
　　　出来ればそれを実装できればなお良しだった

以下の違いを意識しよう
combinations() p, r 長さrのタプル列、ソートされた順で重複なし

combinations_with_replacement() p, r 長さrのタプル列、ソートされた順で重複あり


使用例 　　　　　　　　　　　                  出力　　
combinations('ABCD', 2)　　　　　　　　　　　　AB AC AD BC BD CD

combinations_with_replacement('ABCD', 2)　　 AA AB AC AD BB BC BD CC CD DD
'''

def main():
    N, M, Q = map(int, input().split())#値の読み取り
    abcd = [None] * Q#abccdを入れる箱を作ってる
    for i in range(Q):#値を入力していく
        abcd[i] = tuple(map(int, input().split()))
        #tipleなのは参照だけなので固定かつlistより処理速度の速いものが求められていたため
    ans = 0
    for A in combinations_with_replacement(range(1, M+1), N):
        #1からM+1の数字についてxCNの全探索をし数列を出力しようとしている
        #print(A)
        score = 0
        for q in abcd:#
            #各数列に対してQ通りの計算を試している
            #print(q)
            #qはabcdのtupleが入っている
            a, b, c, d = q#a=q[0], b=q[1]ってことか
            #print(a, b, c, d)
            if A[b-1] - A[a-1] == c:
                score += d
        if score > ans:#値が更新されたときに入れ替えている
            ans = score

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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


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


ans = 0
l = [0] * n
l[0] = 1


def dfs(l_len):
    global l, ans
    if l_len == n:
        ans = max(ans, calc(l))
        return

    for i in range(l[l_len - 1], m + 1):
        l[l_len] = i
        dfs(l_len + 1)


dfs(1)
print(ans)

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())  #数字
Q = [list(map(int, input().split())) for i in range(Q)]  #数字複数列、複数行

import itertools
A = 0
for i in itertools.combinations_with_replacement(range(M),N):
    score = 0
    for j in range(len(Q)):
        if i[Q[j][1]-1] - i[Q[j][0]-1] == Q[j][2]:
            score += Q[j][3]
        if score > A:
            A = score

print(A)

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())  #数字
Q = [list(map(int, input().split())) for i in range(Q)]  #数字複数列、複数行

import itertools
A = []
for i in itertools.combinations_with_replacement(range(M),N):
    score = 0
    for j in range(len(Q)):
        if i[Q[j][1]-1] - i[Q[j][0]-1] == Q[j][2]:
            score += Q[j][3]
        A.append(score)

print(max(A))

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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


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


ans = 0
for l in combinations_with_replacement(range(1, m + 1), n):
    cand = calc(l)
    ans = max(ans, cand)

print(ans)

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(q)]
ans=0
for i1 in range(1,m+1): #愚直に10重ループを行っても、そのループ回数は高々92378回
  for i2 in range(i1,m+1):
    for i3 in range(i2,m+1):
      for i4 in range(i3,m+1):
        for i5 in range(i4,m+1):
          for i6 in range(i5,m+1):
            for i7 in range(i6,m+1):
              for i8 in range(i7,m+1):
                for i9 in range(i8,m+1):
                  for i10 in range(i9,m+1):
                    tmp=0
                    arrs=[0,i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]
                    for a,b,c,d in arr: #条件を満たす数列について、最大値を求める
                      if arrs[b]-arrs[a]==c:
                        tmp+=d
                    ans=max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
def f(n, m, q, requirements):
    A = [1 for i in range(n + 1)]
    ans = 0
    while True:
        # スコア計算
        score = 0
        for requirement in requirements:
            a, b, c, d = requirement
            if A[b] - A[a] == c:
                score += d
        ans = max(ans, score)
        # 数列更新
        j = n
        while j > 0:
            if A[j] < m:
                A[j] += 1
                for i in range(j + 1, n + 1):
                    A[i] = A[j]
                break
            j -= 1
        if j == 0:
            break
    return ans


if __name__ == '__main__':
    n, m, q = map(int, input().split())
    requirements = []
    for i in range(q):
        requirements.append(tuple(map(int, input().split())))
    print(f(n, m, q, requirements))

Submission status: Accepted

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

K= [list(map(int, input().split())) for i in range(Q)]#二次配列

ans = 0
for A in itertools.combinations_with_replacement([i for i in range(1, M + 1)], N):
    ans1 = 0
    for i in range(Q):
        a, b, c, d = K[i]#各数字に配列の値を代入する
        if (A[b - 1] - A[a - 1] == c):
            ans1 += d
        ans = max(ans, ans1)
print(ans)

Submission status: Accepted

Solution code:
import itertools
import copy
import math

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

# process
ans = 0
for a1 in range(1, M+1):
    for a2 in range(a1, M+1):
        for a3 in range(a2, M+1):
            for a4 in range(a3, M+1):
                for a5 in range(a4, M+1):
                    for a6 in range(a5, M+1):
                        for a7 in range(a6, M+1):
                            for a8 in range(a7, M+1):
                                for a9 in range(a8, M+1):
                                    for a10 in range(a9, M+1):
                                        seq = [a1, a2, a3, a4, a5, a6, a7, a8, a9, a10]
                                        t = 0
                                        for a, b, c, d in L:
                                            if seq[b]-seq[a] == c:
                                                t += d
                                        
                                        ans = max(ans, t)

# output
print(ans)

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())  #数字
Q = [list(map(int, input().split())) for i in range(Q)]  #数字複数列、複数行

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

B = []
import itertools
for i in itertools.combinations_with_replacement(A,N):
    B.append(i)

C = []
for i in range(len(B)):
    score = 0
    for j in range(len(Q)):
        if B[i][Q[j][1]-1] - B[i][Q[j][0]-1] == Q[j][2]:
            score += Q[j][3]
        C.append(score)

print(max(C))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import itertools
n, m, q = map(int,input().split())
abcd = []
for i in range(q):
    abcd.append([int(i) for i in input().split()])
"""
#再帰で求める（できない）
A = []
def func(B, n):
    if len(B) == n:
        A.append(B)
        return
    elif len(B) == 0:
        for i in range(1, m+1):
            func(B + [i], n)
    else:
        for i in range(B[-1], m+1):
            func(B + [i], n)
print(A)
"""

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 i in range(q):
    a[i] = abcd[i][0]
    b[i] = abcd[i][1]
    c[i] = abcd[i][2]
    d[i] = abcd[i][3]

A = (list(itertools.combinations_with_replacement(range(1, m + 1), n)))
#print(A)
#print(len(A))
ans = 0
for i in range(len(A)):
    tmp = 0
    #print(A[i])
    for j in range(q):
        if (A[i][b[j]-1] - A[i][a[j]-1]) == c[j]:
            tmp += d[j]
    #print(tmp)
    if ans < tmp:
        ans = tmp
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log
from heapq import heapify, 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 decimal import Decimal
inf = float('inf')
MOD = 1000000007
def INT_(n): return int(n) - 1
def MI(): return map(int, input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n: int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')

n, m, q = MI()
abcd = LLIN(q)

def main():
    data = list(range(1, m+1))
    arr = combinations_with_replacement(data, n)
    ans = 0
    for A in arr:
        tmp = 0
        for a,b,c,d in abcd:
            if A[b-1] - A[a-1] == c:
                tmp += d
            
        ans = max(ans, tmp)
    
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
abcd=[list(map(int,input().split())) for _ in range(q)]
# dfsで数列を生成
def dfs():
  todo=[[]]
  ret=[]
  while len(todo)>0:
    t=todo.pop()
    if len(t)==n:
      ret.append(t)
    else:
      l=t[-1] if len(t)>0 else 1
      for i in range(l,m+1):
        tc=t.copy()
        tc.append(i)
        todo.append(tc)
  return ret
def point(s):# 数列sに対する特典
  ret=0
  for a,b,c,d in abcd:
    if s[b-1]-s[a-1]==c:
      ret+=d
  return ret
a=dfs()
ans=0
for ai in a:
  ans=max(ans,point(ai))
print(ans)

Submission status: Accepted

Solution code:
# 組み合わせはitertoolsを使う

import itertools
N, M, Q = map(int, input().split())
pair = [list(map(int, input().split())) for i in range(Q)]
ans = 0

for A in itertools.combinations_with_replacement(range(1, M+1), N):
    tmp = 0
    for p in pair:
        # pはリスト
        if A[p[1] - 1] - A[p[0] - 1] == p[2]:
            tmp += p[3]
            ans = max(ans, tmp)
            # print("p[1]-1 = ", p[1]-1)
            # print("p[0]-1 = ", p[0]-1)

print(ans)

Submission status: Accepted

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

# len(A) < 10でも、10個数えていいはず。
# 条件に出てこないだけ。

max_score = 0
# 開始値を上位ループの値にすれば単調増加にできる
for A1 in range(1,M+1) :
    for A2 in range(A1, M+1) :
        for A3 in range(A2, M+1) :
            for A4 in range(A3, M+1) :
                for A5 in range(A4, M+1) :
                    for A6 in range(A5, M+1) :
                        for A7 in range(A6, M+1) :
                            for A8 in range(A7, M+1) :
                                for A9 in range(A8, M+1) :
                                    for A10 in range(A9, M+1) :
                                        tmpA = [A1,A2,A3,A4,A5,A6,A7,A8,A9,A10]
                                        tmp_score = 0
                                        for a,b,c,d in cond_list :
                                            if (tmpA[b-1] - tmpA[a-1] == c) :
                                                tmp_score += d
                                        if (max_score < tmp_score) :
                                            max_score = tmp_score

print(max_score)

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
req=[tuple(map(int,input().split())) for i in range(q)]
ans=0
def construction(arr):
    global ans
    if len(arr)==n:
        ret=0
        for i in range(q):
            if arr[req[i][1]-1]-arr[req[i][0]-1]==req[i][2]:ret+=req[i][3]
        ans=max(ret,ans)
        return
    if len(arr)==0:
        for i in range(m):
            construction(arr+[i])
        return
    for i in range(arr[-1],m):
        construction(arr+[i])
    return
construction([])
print(ans)

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(q)]
ans=0
for i1 in range(1,m+1): #愚直に10重ループを行っても、そのループ回数は高々92378回
 for i2 in range(i1,m+1):
   for i3 in range(i2,m+1):
     for i4 in range(i3,m+1):
       for i5 in range(i4,m+1):
         for i6 in range(i5,m+1):
           for i7 in range(i6,m+1):
             for i8 in range(i7,m+1):
               for i9 in range(i8,m+1):
                 for i10 in range(i9,m+1):
                   tmp=0
                   arrs=[0,i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]
                   for a,b,c,d in arr: #条件を満たす数列について、最大値を求める
                     if arrs[b]-arrs[a]==c:
                       tmp+=d
                   ans=max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

def solve(n, m, q, arrays):
    from itertools import combinations_with_replacement
    pattern = list(combinations_with_replacement(range(1, m+1), n))

    maxp = 0
    for x in pattern:
        get = 0
        for array in arrays:
            if x[array[1]-1] - x[array[0]-1] == array[2]:
                get += array[3]

        maxp = max(maxp, get)

    print(maxp)

n, m, q, *aa = map(int, open(0).read().split())

arrays = []
loop = 0
array = []
for x in aa:
    array.append(x)
    loop += 1
    if loop % 4 == 0:
        arrays.append(array)
        array = []

solve(n, m, q, arrays)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log
from heapq import heapify, 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 decimal import Decimal
inf = float('inf')
MOD = 1000000007
def INT_(n): return int(n) - 1
def MI(): return map(int, input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n: int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')

n, m, q = MI()
abcd = LLIN(q)

arr = []
def dfs(A: list):
    if len(A) == n:
        arr.append(A)
        return
    
    if len(A) == 0:
        s = 1
    else:
        s = A[-1]
    
    while s <= m:
        dfs(A + [s])
        s += 1
       

def main():
    dfs([])
    ans = 0
    for A in arr:
        tmp = 0
        for a,b,c,d in abcd:
            if A[b-1] - A[a-1] == c:
                tmp += d
        ans = max(ans, tmp)
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

ans = 0

for v in itertools.combinations(range(N+M-1), N):
    l = []
    for i in range(N):
        l.append(v[i]-i+1)

    total = 0
    for i in range(Q):
        if l[S[i][1]-1] - l[S[i][0]-1] == S[i][2]:
            total += S[i][3]
    
    ans = max(ans, total)

print(ans)

Submission status: Accepted

Solution code:
import itertools
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[i],b[i],c[i],d[i]=map(int,input().split())
    a[i]-=1
    b[i]-=1
ans=0
buf=[None]*n

def dfs(nowdigit,cannum):
    global ans
    if nowdigit==n:
        tmp=0
        for j in range(q):
            if buf[b[j]] - buf[a[j]] == c[j]:
                tmp+=d[j]
        ans=max(ans,tmp)
    else:
        for i in range(cannum,m+1):
            buf[nowdigit]=i
            dfs(nowdigit+1,i)
dfs(0,1)
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

A = []
for _ in range(Q):
    A.append(tuple(map(int,input().split())))
#print(A)
cnt = 0
ans = 0
for i in comb:
    for k in range(Q):
        a = A[k][0]
        b = A[k][1]
        c = A[k][2]
        d = A[k][3]
        if i[b-1] - i[a-1] == c:
            cnt += d
    ans = max(ans,cnt)
    cnt = 0
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
N,M,Q=map(int,input().split())
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())
    b[i]-=1
    a[i]-=1
for i in combinations_with_replacement(range(M),N):
    kari=0
    for j in range(Q):
        if i[b[j]]-i[a[j]]==c[j]:
            kari+=d[j]
    ans=max(kari,ans)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools
N,M,Q = map(int, input().split())
L = [list(map(int, input().split())) for i in range(Q)]
tmp = [k+1 for k in range(M)]
ans = 0
for A in itertools.combinations_with_replacement(tmp,N):
    pre_ans = 0
    for i in range(Q):
        a,b,c,d = L[i]
        if A[b-1] - A[a-1] == c:
            pre_ans += d
        ans = max(ans,pre_ans)
print(ans)

Submission status: Accepted

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

A_list = [1] * N
ans = 0

def calc_score():
  score = 0
  for i in range(Q):
    a, b, c, d = A[i][0], A[i][1], A[i][2], A[i][3]
    if A_list[b-1] - A_list[a-1] == c:
      score += d
  return score
      
def dfs(position, minimum):
  global ans
  if position == N:
    score = calc_score()
    ans = max(ans, score)
    return
  
  for i in range(minimum, M+1):
    A_list[position] = i
    dfs(position+1, i)
    
dfs(1, 1)
print(ans)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

n, m, q = MAP()
'''
arr = [[]]
for i in range(n):
    tmp = deepcopy(arr)
    arr = []
    for j in range(1, m + 1):
        for k in range(len(tmp)):
            if len(tmp[k]) == 0 or tmp[k][-1] <= j:
                arr.append(deepcopy(tmp[k]))
                arr[-1].append(j)
'''
arr = list(combinations_with_replacement(range(1, m + 1), n))
point = [0 for _ in range(len(arr))]
for i in range(q):
    a, b, c, d = MAP()
    for j in range(len(arr)):
        if arr[j][b - 1] - arr[j][a - 1] == c:
            point[j] += d

print(max(point))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

def culc(List):
    global Q
    global commands

    score=0
    for i in range(Q):
        if List[commands[i][1]-1]-List[commands[i][0]-1]==commands[i][2]:
            score+=commands[i][3]
    return score



def max_score(List,last_number):
    global M
    global N
    global Q

    Max_score=0
    temp_score=0
    for i in range(last_number,M+1):
        List.append(i)
        if len(List)==N:
            temp_score=culc(List)
            Max_score=max(Max_score,temp_score)
        else:
            temp_score=max_score(List,i)
            Max_score=max(Max_score,temp_score)
        List.pop(-1)    #backtrack
    
    return Max_score


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


ans=max_score([],1)
print(ans)

Submission status: Accepted

Solution code:
import itertools
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-1, b-1, c, d))
    score = 0
    for ones in list(itertools.combinations([i for i in range(N+M-1)], M-1)):
        temp = [0] * (N + M -1)
        for idx in ones:
            temp[idx] = 1
        A = [0] * N
        idx = 0
        sum_ = 0
        for i in temp:
            if i == 0:
                A[idx] = sum_ + 1
                idx += 1
            else:
                sum_ += 1
        score_temp = get_score(A, abcd)
        if score_temp > score:
            score = score_temp
    print(score)
            
def get_score(A, abcd):
    score = 0
    for a, b, c, d in abcd:
        if A[b] - A[a] == c:
            score += d
    return score

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
def main():
    N, M, Q = (int(_) for _ in input().split())
    query = [[int(_) for _ in input().split()] for __ in range(Q)]
    ret = 0
    for ll in itertools.combinations_with_replacement(range(1, M+1), N):
        cc = 0
        for a, b, c, d in query:
            a, b = a-1, b-1
            if ll[b] - ll[a] == c: cc += d
        ret = max(ret, cc)
    print(ret)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
ans = 0

def dfs():
    global ans
    if len(A) == n:
        count = 0
        for i in range(q):
            if A[b[i] - 1] - A[a[i] - 1] == c[i]:
                count += d[i]
        if count > ans: ans = count
        if A[-1] != m:
            A[-1] += 1
            dfs()
        else:
            A.pop(-1)
        return
    else:
        A.append(A[-1])
        dfs()
        if A[-1] != m:
            A[-1] += 1
            dfs()
        else:
            A.pop(-1)
        return

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 = []

for i in range(1,m + 1):
    A.append(i) 
    dfs()
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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)

a_list = []
  
for i in range(m):
  a_list.append(i)

suuretsu_list = itertools.combinations_with_replacement(a_list, n)

point_list = [0]

for suuretsu in suuretsu_list:
  point = 0
  for _a, _b, _c, _d in zip(a, b, c, d):
    if suuretsu[_b - 1] - suuretsu[_a - 1] == _c:
      point += _d
  point_list.append(point)
print(max(point_list))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
ANS = 0
SUM = 0
def dfs(arr, l):
    global SUM, ANS
    if l == N:
        for i in range(Q):
            if arr[A[i][1]-1]-arr[A[i][0]-1] == A[i][2]:
                SUM += A[i][3]
            ANS = max(SUM, ANS)
        SUM = 0
        return
    else:
        for i in range(arr[l-1], M+1):
            arr.append(i)
            l = len(arr)
            dfs(arr,l)
            arr.pop()

    return ANS

if __name__ == '__main__':
    N, M ,Q = map(int, input().split())
    A = [list(map(int, input().split())) for i in range(Q)]
    for i in range(M):
        pANS = ANS
        ARR = deque([i+1])
        dfs(ARR,1)
        ANS = max(pANS, ANS)
    print(ANS)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
ANS = 0
SUM = 0
def dfs(arr, l):
    global SUM, ANS
    # print(arr)
    if l == N:
        for i in range(Q):
            # print(arr[A[i][1]-1]-arr[A[i][0]-1])

            if arr[A[i][1]-1]-arr[A[i][0]-1] == A[i][2]:
                SUM += A[i][3]
            ANS = max(SUM, ANS)
        SUM = 0
        return
    else:
        for i in range(arr[l-1], M+1):
            arr.append(i)
            l = len(arr)
            # print(arr)
            dfs(arr,l)
            arr.pop()

    return ANS

if __name__ == '__main__':
    N, M ,Q = map(int, input().split())
    A = [list(map(int, input().split())) for i in range(Q)]
    ARR = deque([1])
    dfs(ARR,1)
    print(ANS)