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


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


resolve()

Submission status: Accepted

Solution code:
N,M,Q=map(int,input().split())
R=[list(map(int,input().split())) for i in range(Q)]
S=[1]*N#1がNこ入った配列　
 
def dfs(d):
    if d==N-1:
        t=0
        for a,b,c,d in R:
            if S[b-1]-S[a-1]==c:
                t+=d
        return t
    else:
        m=0
        for i in range(S[d],M+1):
            S[d+1]=i
            m=max(m,dfs(d+1))
        return m

print(dfs(0))

Submission status: Accepted

Solution code:
import itertools
n, m, q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(q)]
li = list(itertools.combinations_with_replacement(range(1, m+1), n))
ans = 0
for l in li:
    result = 0
    for line in abcd:
        if (l[line[1]-1]-l[line[0]-1]) == (line[2]):
            result += line[3]
    ans = max(ans, result)
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

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

Submission status: Accepted

Solution code:
import itertools
n,m,q=map(int,input().split())
lis=[]
ans=0

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# C - Many Requirements
# DFSで解く

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

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

ans = 0
print(dfs([1]))

Submission status: Accepted

Solution code:


from functools import lru_cache

n, m, q = map(int, input().split())
abc2d = {}
a2bcd = {}
for i in range(q):
    a,b,c,d = map(int, input().split())
    a -= 1
    b -= 1
    abc2d[a,b,c] = d
    a2bcd.setdefault(a, [])
    a2bcd[a].append((b,c,d))

a = [0] * n # 各要素は0,1,...,m-1
best = 0

@lru_cache(2**20)
def value(ind, *tmp_a):
    # a[ind:]についての目的関数値, *tmp_aはa[ind](=0), a[ind+1],...が入る
    val = 0
    if ind in a2bcd:
        val = value(ind+1, *(item-tmp_a[0] for item in tmp_a[1:]))
        for bb,cc,dd in a2bcd[ind]:            
            if tmp_a[bb-ind] - tmp_a[0] == cc:
                val += dd
#     print(tmp_a, val)
    return val

def sub(a,ind):
    global best
    # a[ind:]について全探索
    if ind==n:
        val = value(0,*a)
        best = max(best, val)
        return
    for v in range(a[ind-1], m):
        a[ind] = v
        sub(a, ind+1)
sub(a, 1)
print(best)

Submission status: Accepted

Solution code:
import itertools
N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]
M_chr = []
for i in range(1,M+1):
    M_chr.append(i)
As = list(itertools.combinations_with_replacement(M_chr, N))
pointA_max = 0
for i, A in enumerate(As):
    pointA = 0
    for i in range(Q):
        if A[abcd[i][1]-1]-A[abcd[i][0]-1] == abcd[i][2]:
            pointA = pointA + abcd[i][3]
    if pointA_max < pointA:
        pointA_max = pointA
print(pointA_max)

Submission status: Accepted

Solution code:
# C
from itertools import combinations_with_replacement
n, m, q = map(int, input().split())
l = [list(map(int, input().split())) for i in range(q)]
# print(l)
l.sort(key=lambda x: x[3], reverse=True)
# 順列A全捜索
# 1~mまでの値を持った長さnの順列を i に出力する。
# >>combinations_with_replacement()
# print(combinations_with_replacement(range(1, m + 1), n))

ans = 0
for i in combinations_with_replacement(range(1, m + 1), n):
    # print(i)
    t = 0
    #列を出力
    for a, b, c, d in l:
        # print(a, b, c, d)
        #条件が合うなら +d
        if i[b - 1] - i[a - 1] == c:
            t += d
    # ansが大きい値を出力
    ans = max(t, ans)
print(ans)

Submission status: Accepted

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

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

for i in itertools.combinations_with_replacement(ele,n):
    a = list(i)
    d = 0
    for j in range(q):
        if a[x[j][1]-1] - a[x[j][0]-1] == x[j][2]:
            d += x[j][3]
    ans = max(ans,d)
print(ans)

Submission status: Accepted

Solution code:
from itertools import *

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

aaa=[int(i) for i in range(1,m+1)]
a=list(combinations_with_replacement(aaa,n))

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


ans=0

for i in a:
    aa=0
    for j in l:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            aa+=j[3]
    if aa>ans:
        ans=aa
print(ans)

Submission status: Accepted

Solution code:
import itertools

def check(lis, a):
    return sum([i[3] for i in a if lis[i[1]-1]-lis[i[0]-1]==i[2]])
   
n, m, q = map(int, input().split())
a = [[int(i) for i in input().split(" ")] for j in range(q)]
ans = 0
for i in itertools.combinations_with_replacement(range(m), n):
    ans = max(ans, check(i, a))
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
a = [i for i in range(1,M+1)]

for A in itertools.combinations_with_replacement(a,N):
    tmp = 0
    for l in li:
        if A[l[1]-1] - A[l[0]-1] == l[2]:
            tmp += l[3]
    else:
        ans = max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import math
n, m, q = map(int,input().split())
max = 0
j = []
for i in range(q):
    aa,b,c,d = map(int,input().split())
    j.append([aa,b,c,d])

a = [0 for k in range(11)]
for i1 in range(1,11):
    a[1] = i1
    for i2 in range(i1,m+1):
        a[2] = i2
        for i3 in range(i2,m+1):
            a[3] = i3
            for i4 in range(i3,m+1):
                a[4] = i4
                for i5 in range(i4,m+1):
                    a[5] = i5
                    for i6 in range(i5,m+1):
                        a[6] = i6
                        for i7 in range(i6,m+1):
                            a[7] = i7
                            for i8 in range(i7,m+1):
                                a[8] = i8
                                for i9 in range(i8,m+1):
                                    a[9] = i9
                                    for i10 in range(i9,m+1):
                                        a[10] = i10
                                        s = 0
                                        for i in j:
                                            if a[i[1]]-a[i[0]] == i[2]:
                                                s += i[3]
                                        if max < s:
                                            max = s

print(max)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations_with_replacement as combi
input = sys.stdin.readline
N, M, Q = map(int, input().split())
qs = [tuple(map(int, input().split())) for _ in range(Q)]
res = 0
for c in combi([x for x in range(1, M + 1)], N):
  t = 0
  for l, r, d, s in qs:
    if c[r - 1] - c[l - 1] == d: t += s
  res = max(res, t)
print(res)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7
ans = 0


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

    A = [0] * n

    def dfs(idx):
        global ans
        if idx == n:
            score = 0
            for i in range(q):
                a, b, c, d = ABCD[i]
                if A[b - 1] - A[a - 1] == c:
                    score += d
            ans = max(ans, score)
        else:
            if idx == 0:
                k = 1
            else:
                k = A[idx - 1]

            for i in range(k, m + 1):
                A[idx] = i
                dfs(idx + 1)

    dfs(0)
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
#!/usr/bin/python3
import math
import copy

def getp(qs, cl):
    p = 0
    for (a, b, c, d) in qs:
        if cl [b - 1] - cl[a - 1] == c:
            p += d
    return p

def maxp(qs, idx, cl, n, m):
    p = 0    
    if idx == n - 1:
        for i in range(cl[idx - 1], m + 1):
            cl[idx] = i
            p = max(p, getp(qs, cl))
    else:
        for i in range(cl[idx - 1], m + 1):
            cl[idx] = i
            p = max(p, maxp(qs, idx + 1, cl, n, m))
    return p        
    
(n, m, q) = map(int, input().split())

qs = []
for i in range(q):
    qs.append(tuple(map(int, input().split())))

qs.sort()
         
l = [ 0 for i in range(n) ]
l[0] = 1
cache = {}

print(maxp(qs, 1, l, n, m))

Submission status: Accepted

Solution code:
import itertools
N,M,Q = map(int,input().split())
x = [list(map(int,input().split()))  for _ in range(Q)]
d=0
ans=0
B=[]

#Aの場合の数を全列挙
ele = [k for k in range(1,M+1)]

for i in itertools.combinations_with_replacement(ele,N):
  A = list(i)
  d=0
  for j in range(Q):
    if A[x[j][1]-1] - A[x[j][0]-1] == x[j][2]:
      d += x[j][3]
      
  else:
    if d>ans:
      ans = d
     
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#実験
# -*- coding: utf-8 -*-
n, m, q = map(int, input().split())
integer_set = [list(map(int, input().split())) for _ in range(q)]
a = [1]
score = 0
 
# 深さ優先探索(Depth First Search)
def dfs(seq):
    if len(seq) == n:
        global score
        tmp_score = 0
        for a, b, c, d in integer_set:
            if seq[b-1] - seq[a-1] == c:
                tmp_score += d
            else:
                tmp_score += 0
        score = max(score, tmp_score)
    else:
        for i in range(seq[-1], m+1):
            tmp_seq = seq.copy()
            tmp_seq.append(i)
            dfs(tmp_seq)
 
dfs(a)
print(score)

Submission status: Accepted

Solution code:
N,M,Q=map(int,input().split())
R=[list(map(int,input().split())) for i in range(Q)]
S=[1]*N

def dfs(d):
  if d==N-1:
    t=0
    for a,b,c,d in R:
      if S[~-b]-S[~-a]==c:
        t+=d
    return t
  else:
    m=0
    for i in range(S[d],M+1):
      S[d+1]=i
      m=max(m,dfs(d+1))
    return m

print(dfs(0))

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

res = 0
for arr in combinations_with_replacement(range(1, m+1), n):
    score = 0
    for a, b, c, d in abcd:
        if arr[b-1] - arr[a-1] == c:
            score += d
    if score > res:
        res = score

print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat May  2 20:59:14 2020
"""

import sys
#import numpy as np
import itertools
sys.setrecursionlimit(10 ** 9)

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

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

ans = 0
for l in A:
    tmp = 0
    for a,b,c,d in abcd:
        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())
abcd = [list(map(int, input().split())) for _ in range(Q)]

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

Submission status: Accepted

Solution code:
#coding: utf-8
from itertools import combinations_with_replacement
N, M, Q = map(int, input().split())
li = list(combinations_with_replacement([i for i in range(1, M+1)], N))
eq = []
for i in range(Q):
    eq.append(list(map(int, input().split())))
# print(list(combinations_with_replacement([i for i in range(1, M+1)], N)))
ans = 0
for l in li:
    tmp = 0
    for i in range(Q):
        a, b, c, d = eq[i]
        if l[b-1] - l[a-1] == c:
            tmp += d
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:

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

def calc_score(score):
    ret = 0
    for i in range(q):
        if score[b[i] - 1] - score[a[i] - 1] == c[i]:
            ret += d[i]
    return ret

def dfs(score, i, num):
    global ans
    if i == n:
        ans = max(ans, calc_score(score))
        return 
    for j in range(num, m + 1):
        score[i] = j
        dfs(score, i + 1, j)


dfs(score, 0, 1)
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)]
from itertools import combinations_with_replacement
A = list(combinations_with_replacement(range(1,m+1),n))
#print(A)
ans = 0
for i in range(len(A)):
    point = 0
    for j in range(q):
        if A[i][abcd[j][1]-1] - A[i][abcd[j][0]-1] == abcd[j][2]:
            point += abcd[j][3]
    ans = max(ans, point)
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

maxScore = 0
for x in array:
    score = 0
    for y in abcd:
        if x[y[1] - 1] - x[y[0] - 1] == y[2]:
            score += y[3]
    maxScore = max(maxScore, score)
print(maxScore)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

sys.setrecursionlimit(10 ** 6)

n, m, q = na()
abcd = nan(q)

ans = 0
def dfs(s):
    if len(s) == n + 1:
        res = 0
        for i in range(q):
            a, b, c, d = abcd[i]
            if s[b] - s[a] == c:
                res += d
        return res
    res = 0
    for i in range(s[-1], m + 1):
        news = s[:]
        news.append(i)
        res = max(res, dfs(news))
    return res

print(dfs([1]))

Submission status: Accepted

Solution code:
import copy
n,m,q=map(int,input().split())
abcd = [map(int, input().split()) for _ in range(q)]
a,b,c,d=[list(i) for i in zip(*abcd)]
ans=0

def dfs(B):

    global ans,n,m,q,a,b,c,d
    A=copy.deepcopy(B)
    if(len(A)==n+1):
        now=0
        for i in range(q):
            if A[b[i]]-A[a[i]]==c[i]:
                now += d[i]
        
        ans = max(ans,now)
       # A.append(now)
       # print(A)
        return
    
    A.append(A[-1])
    while(A[-1]<=m):
        dfs(A)
        A[-1]=A[-1]+1

        
B=[1,1]
dfs(B)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May  3 12:03:48 2020

@author: ybt07
"""

from collections import deque

# 入力
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())

def dfs(A):

    global ans
    
    # A = [(1), 1, 2, 2,...] と、先頭の 1 はダミー的に使用しているので、深さ N+1 で計算
    # 深さが N+1 まで来たら、値を計算
    if len(A) == N+1:  # 直前で M をコピーされて来たので
        now = 0

        # 得点計算
        for i in range(Q):
            if A[b[i]] - A[a[i]] == c[i]:
                now += d[i]
            
        ans = max(ans, now)  # 最高値の更新        
        return
    
    # 再帰呼出し部
    # （長さがN以下なので）末尾に要素を追加して（＝一段深くして）探索
    tmp = A[len(A)-1]
    while True:

        if tmp > M:
            break

        A.append(tmp)
        dfs(A)
        A.pop()
        tmp += 1

# main
ans = 0  # 値
A = deque([1]) # 後ろへコピーするための初期値　兼　インデックスを合わせる

dfs(A)

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

a = [0]*q
b = [0]*q
c = [0]*q
d = [0]*q

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

ans = 0

for comb in itertools.combinations_with_replacement(range(1, m+1), n):
	j = 0
	for i in range(q):
		if comb[b[i]-1]-comb[a[i]-1] == c[i]:
			j += d[i]
	#print('{} {}'.format(comb, j))
	ans = max(ans, j)

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as cmb

n,m,q=map(int,input().split())
abcd=[]
for i in range(q):
    ll=map(int,input().split())
    ll=[ww-1 for ww in ll]
    abcd.append(ll)
ans=0
for li in cmb(range(1,m+1),n):
    kari=0
    for i in abcd:
        if li[i[1]]-li[i[0]]==i[2]+1:
            kari+=i[3]+1
    ans=max(ans,kari)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n, m, q = map(int, input().split())
integer_set = [list(map(int, input().split())) for _ in range(q)]
a = [1]
score = 0

# 深さ優先探索(Depth First Search)
def dfs(seq):
    if len(seq) == n:
        global score
        tmp_score = 0
        for a, b, c, d in integer_set:
            if seq[b-1] - seq[a-1] == c:
                tmp_score += d
            else:
                tmp_score += 0
        score = max(score, tmp_score)
    else:
        for i in range(seq[-1], m+1):
            tmp_seq = seq.copy()
            tmp_seq.append(i)
            dfs(tmp_seq)

dfs(a)
print(score)

Submission status: Accepted

Solution code:
import itertools

N,M,Q = map(int,input().split())
a=[]
b=[]
c=[]
d=[]
for i in range(0,Q,1):
    tmp = list(map(int,input().split()))
    a.append(tmp[0])
    b.append(tmp[1])
    c.append(tmp[2])
    d.append(tmp[3])

max_score = -1
for i in itertools.combinations_with_replacement(range(1,M+1,1),N):
    score = 0
    for j in range(0,Q,1):
        if i[b[j]-1]-i[a[j]-1]==c[j]:
            score += d[j]
    if max_score < score:
        max_score = score

print(max_score)

Submission status: Accepted

Solution code:
import copy

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

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


A_list =[-1] * N
sum_max = 0

A_list_list =[]

def dfs(curr, count):
    if count >= N:
        sum_ = 0
        
        for q in range(Q):
            ai = abcd_list[q][0]
            bi = abcd_list[q][1]
            ci = abcd_list[q][2]
            di = abcd_list[q][3]

            if A_list[bi - 1] - A_list[ai - 1] == ci:
                sum_ += di
        global sum_max
        if sum_max <= sum_:
            sum_max = sum_

        A_list_list.append(copy.copy(A_list))

        return

    # 次の値を求める
    for i in range(curr, M + 1):
        A_list[count] = i
        dfs(i, count + 1)

dfs(1, 0)
print(sum_max)

Submission status: Accepted

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

for i1 in range(1, m+1):
    for i2 in range(i1, m+1):
        for i3 in range(i2, m+1):
            for i4 in range(i3, m+1):
                for i5 in range(i4, m+1):
                    for i6 in range(i5, m+1):
                        for i7 in range(i6, m+1):
                            for i8 in range(i7, m+1):
                                for i9 in range(i8, m+1):
                                    for i10 in range(i9, m+1):
                                        arr = [i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]
                                        tmp = 0
                                        for a, b, c, d in abcd:
                                            if arr[b - 1] - arr[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())
m = list()
res = -100
for i in range(Q):
    n = list(map(int, input().split()))
    m.append(n)
l = [x for x in range(1, M + 1)]
p = itertools.combinations_with_replacement(l, N)
for p in p:
    total = 0
    for i in range(Q):
        a = m[i][0]
        b = m[i][1]
        A = p[a - 1]
        B = p[b - 1]
        C = B - A
        if m[i][2] == C:
            total = total + m[i][3]
    if res < total:
        res = total
print(res)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 11
import sys
sys.setrecursionlimit(100000000)
from itertools import combinations_with_replacement

def main():
    N,M,Q = map(int,input().split())
    ABCD = [tuple(map(int,input().split())) for _ in range(Q)]
    
    ans = 0
    for cmb in combinations_with_replacement(range(M),N):
        score = 0
        for a,b,c,d in ABCD:
            if cmb[b - 1] - cmb[a - 1] == c:
                score += d
        ans = max(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())
lis = [list(map(int, input().split())) for i in range(q)]

ans = 0

for l in list(combinations_with_replacement(range(1, m+1), n)):
    S = 0
    for a, b, c, d in lis:
        if l[b-1] - l[a-1] == c:
            S += d
    if ans < S:
            ans = S

print(ans)

Submission status: Accepted

Solution code:
import itertools

mMNQ = map(int, input().split())
lMNQ = list(mMNQ)

mPts = [map(int, input().split()) for i in range(lMNQ[2])]
lPts = [list(j) for j in mPts]

lNum = range(1, lMNQ[1] + 1)

lSet = itertools.combinations_with_replacement(lNum, r = lMNQ[0])
lSet = list(lSet)

pMax = 0
for s in lSet:
    sum = 0
    
    for p in lPts:
        if(s[p[1]-1] - s[p[0]-1] == p[2]):
            sum += p[3]
    
    if(sum > pMax):
        pMax = sum
        
print(pMax)

Submission status: Accepted

Solution code:
import math
import itertools

N, M, Q = map(int, input().split())
a = [0]*Q
b = [0]*Q
c = [0]*Q
d = [0]*Q
for i in range(Q):
    a[i], b[i], c[i], d[i] = map(int, input().split())
Al = [0]*M
for i in range(M):
    Al[i] = i + 1
All = list(itertools.combinations_with_replacement(Al, N))

ans = 0

for A in All:
    wa = 0
    for i in range(Q):
        kari = A[b[i]-1] - A[a[i] - 1]
        if kari == c[i]:
            wa = wa + d[i]
    if ans < wa:
        ans = wa
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
n,m,q = [int(i) for i in readline().split()]
abcd = [[int(i) for i in readline().split()] for _ in range(q)]

ans = 0

def dfs(A):
    if len(A) == n:
        now = 0
        for a, b, c, d in abcd:
            if A[b-1] - A[a-1] == c: # a,bは1始まりの値になっているので、indexとして使う時は-1する
                now += d
        global ans
        ans = max(ans, now)
    else:
        for i in range(A[-1], m+1):
            dfs(A+[i])

for i in range(1, m+1):
    dfs([i])

print(ans)

Submission status: Accepted

Solution code:
import itertools
N, M, Q = map(int, input().split())
par = []
for _ in range(Q):
    par.append([int(x) for x in input().split()])

ans = 0
for A in itertools.combinations_with_replacement(range(M), N):
#     print(A)
    temp = 0
    for i in range(Q):
        if A[par[i][1]-1] - A[par[i][0]-1] == par[i][2]:
            temp += par[i][3]
    ans = max(ans, temp)
print(ans)

Submission status: Accepted

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

import itertools

seq_list = itertools.combinations_with_replacement(range(1, m + 1), n)
max_score = 0

for seq in seq_list:
    temp_max = 0
    for j in l:
        if seq[j[1] - 1] - seq[j[0] - 1] == j[2]:
            temp_max += j[3]
    max_score = max(max_score, temp_max)

print(max_score)

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
abcd_li = [list(map(int, input().split())) for _ in range(Q)]
ans = 0
for i1 in range(1, M + 1):
    for i2 in range(i1, M + 1):
        for i3 in range(i2, M + 1):
            for i4 in range(i3, M + 1):
                for i5 in range(i4, M + 1):
                    for i6 in range(i5, M + 1):
                        for i7 in range(i6, M + 1):
                            for i8 in range(i7, M + 1):
                                for i9 in range(i8, M + 1):
                                    for i10 in range(i9, M + 1):
                                        arr = [
                                            0,
                                            i1,
                                            i2,
                                            i3,
                                            i4,
                                            i5,
                                            i6,
                                            i7,
                                            i8,
                                            i9,
                                            i10,
                                        ]
                                        tmp = 0
                                        for a, b, c, d in abcd_li:
                                            if arr[b] - arr[a] == c:
                                                tmp += d
                                            ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
import math
import itertools

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




Al =[0] * M
for i in range(M):
    Al[i] = i+1


#Nの値が小さそうなので全検索でもいけるかもしれへん。
#Nの値が小さそうなので全検索でもいけるかもしれへん。
#Nの値が小さそうなので全検索でもいけるかもしれへん。
#Nの値が小さそうなので全検索でもいけるかもしれへん。
#Nの値が小さそうなので全検索でもいけるかもしれへん。
#Nの値が小さそうなので全検索でもいけるかもしれへん。
#Nの値が小さそうなので全検索でもいけるかもしれへん。
#Nの値が小さそうなので全検索でもいけるかもしれへん。
#Nの値が小さそうなので全検索でもいけるかもしれへん。
All = list(itertools.combinations_with_replacement(Al, N))


#M個のうちからN個取り出す順列
ans = 0
#for A in itertools.combinations(All, N):
for A in All:
    #点数計算
    #print(A)
    wa = 0
    for i in range(Q):
        #print(wa) 
        kari = A[b[i]-1] - A[a[i]-1]
        if kari == c[i]:
            wa = wa + d[i] 
    if ans < wa:
        ans = wa
    #print(ans) 
    #print(wa) 


print(ans)

Submission status: Accepted

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

for li in itertools.combinations_with_replacement(range(1,m+1),n):
    sum_d = 0
    for i in range(q):
        if li[b[i]-1]-li[a[i]-1] == c[i]:
            sum_d+=d[i]
    if sum_d > ans:
        ans = sum_d
print(ans)

Submission status: Accepted

Solution code:
def dfs(nums, length, right_num):
    max_score = 0
    if length == N:
        score = 0
        for a,b,c,d in req:
            if nums[b] - nums[a] == c:
                score += d
        return score
    else:
        for num in range(right_num,M+1):
            new_nums = nums + [num]
            score = dfs(new_nums,length+1,num)
            max_score = max(max_score,score)
    return max_score        

N,M,Q = map(int,input().split())
req = [list(map(int,input().split())) for _ in range(Q)]
print(dfs([-1],0,1))

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
abcd=[list(map(int,input().split())) for _ in range(q)]
ans,now=0,0
def chk(x):
    global ans
    if len(x)>=n+1:
        now=0
        for a,b,c,d in abcd:
            if x[b-1]-x[a-1]==c:
                now+=d
        ans=max(ans,now)
        return
    for i in range(x[-1],m+1):
        chk(x+[i])
chk([1])
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
from itertools import combinations
def run():
    N,M,Q = map(int, sysread().split())
    cri = []
    for _ in range(Q):
        cri.append(list(map(int,sysread().split())))

    ret = 0

    S = list(range(1, N+M))
    for j in combinations(S, N):
        tmp_arr = [j[0]]
        pre_val = j[0]
        for idx, val in enumerate(j[1:],1):
            tmp_arr.append(tmp_arr[idx-1] + val - pre_val - 1)
            pre_val = j[idx]
        total = 0
        for a,b,c,d in cri:
            a -= 1
            b -= 1
            if tmp_arr[b] - tmp_arr[a] == c:
                total += d
        ret = max(ret, total)
    print(ret)

if __name__ == "__main__":
    run()