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:
from itertools import combinations_with_replacement

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

ans = 0
for v in combinations_with_replacement(range(1, m+1), n):
    A = list(v)
    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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from __future__ import print_function

import sys
sys.setrecursionlimit(500000)

import re
import array
import copy
import functools
import operator

import math
import string
import fractions
from fractions import Fraction

import collections
import itertools
import bisect

import random
import time

import heapq
from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import heapreplace
from queue import PriorityQueue as pq
from queue import Queue

from itertools import accumulate

from collections import deque
from collections import Counter

from operator import mul
from functools import reduce

input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

# from fractions import gcd
# from math import gcd

# def lcm(n, m):
#     return int(n * m / gcd(n, m))


# def coprimize(p, q):
#     common = gcd(p, q)
#     return (p // common, q // common)


# def find_gcd(list_l):
#     x = reduce(gcd, list_l)
#     return x


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def main():
    # 
    n,m,q = map(int,input().strip().split())
    abcd = []
    for i in range(q):
        # a,bはindexの次元，cは値， dはポイント
        temp_a,temp_b,temp_c,temp_d = map(int,input().strip().split())
        abcd.append((temp_a - 1, temp_b - 1, temp_c, temp_d ))

    # 
    eprint('n,m,q ',end=':\n')
    eprint(n,m,q)
    eprint('abcd ',end=':\n')
    eprint(abcd)

    #
    ans=0
    ll=[i for i in range(1,m+1)]
    # # ll=[i for i in range(1,m+1)]+[i for i in range(1,m+1)]+[i for i in range(1,m+1)]+[i for i in range(1,m+1)]
    # A=[]
    # rep(n)
    # for a1 in range(1,m+1):
    #     for a2 in range(p,m+1):
    #         for a3 in range(j,m+1):
    #             for a4 in range(k,m+1):
    #                 for a5 in range(k,m+1):
    #                     for a6 in range(k,m+1):
    #                         for a7 in range(k,m+1):
    #                             for a8 in range(k,m+1):
    #                                 for a9 in range(k,m+1):
    #                                     if :
    #                                         pass
    #                     pass
    #                 A=[p,j,k,l]
    #                 point = 0
    #                 for i in range(q):
    #                     a=abcd[i][0]
    #                     b=abcd[i][1]
    #                     c=abcd[i][2]
    #                     d=abcd[i][3]
    #                     if A[b] - A[a] == c:
    #                         point+=d
    #                 ans = max(point,ans)
    # print(ans)   
    for A in itertools.combinations_with_replacement(ll,n):
        #
        eprint('A ',end=':\n')
        eprint(A)

        point = 0
        for i in range(q):
            a=abcd[i][0]
            b=abcd[i][1]
            c=abcd[i][2]
            d=abcd[i][3]
            if A[b] - A[a] == c:
                point+=d
        ans = max(point,ans)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

from itertools import combinations_with_replacement as cwr

def main():
    N, M, Q = map(int, input().split())
    I = [list(map(int, input().split())) for _ in range(Q)]
    J = cwr(range(1, M+1), N)
    ans = []

    for j in J:
        tmp = 0
        for i in I:
            a, b, c, d = i
            tmp += d if j[b-1] - j[a-1] == c else 0
        ans.append(tmp)

    print(max(ans))

    
if __name__  == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

n, m, q = map(int, input().split())
I = list(range(1, m + 1))
A = list(map(list, itertools.combinations_with_replacement(I, n)))
l = len(A)
ans = [0 for i in range(l)]
for _ in range(q):
    a, b, c, d = map(int, input().split())
    for i in range(l):
        if A[i][b - 1] - A[i][a - 1] == c:
            ans[i] += d
print(max(ans))

Submission status: Accepted

Solution code:

from itertools import combinations_with_replacement

def resolve():
    N, M, Q = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(Q)]
    cmb_A = list(combinations_with_replacement(range(1,M+1), N))

    ans = 0
    for cmb in cmb_A:
        tot = 0
        for x in A:
            a,b,c,d = x
            a -= 1
            b -= 1
            if cmb[b]-cmb[a] == c:
                tot += d
        ans = max(ans, tot)
    print(ans)

if __name__ == "__main__":
    resolve()

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())
A_list = []
for p in itertools.combinations_with_replacement(range(1,m+1),n):
    A_list.append(p)
# print(A_list)

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

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
def main():
    N, M, Q = map(int, input().split())
    abcd = [list(map(int, input().split())) for _ in range(Q)]
    ans = 0
    for x in combinations_with_replacement(range(1, M+1), N):
        point = 0
        for a, b, c, d in abcd:
            if x[b-1] - x[a-1] == c:
                point += d
        if ans < point:
            ans = point
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 2020/05/02
# AtCoder Beginner Contest 165 - C

a = list()
def mkArray(in_list, sav_val, cnt):
    if cnt >= n:
        a.append(in_list)
        return 0
    else:
        for x in range(sav_val, m + 1):
            wk_list = list()
            wk_list.extend(in_list)
            wk_list.append(x)
            mkArray(wk_list, x, cnt + 1)

# Input
n, m, q = map(int,input().split())
abcd = list()

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

# Make Array
w_a = list()
mkArray(w_a, 1, 0)

# Search
ans = 0
for i in range(len(a)):
    wans = 0
    for j in range(q):
        if a[i][abcd[j][1]-1] - a[i][abcd[j][0]-1] == abcd[j][2]:
            wans = wans + abcd[j][3]

    if wans > ans:
        ans = wans

# Output
print(ans)

Submission status: Accepted

Solution code:
import itertools

def calc(A_list):
    ans = 0
    for A in A_list:
        score = 0     
        for i in range(Q):
            a, b, c, d = X[i]
            if A[b-1] -A[a-1] == c:
                score += d
        ans = max(ans, score)
    return ans

N, M, Q = map(int, input().split())
X = [[0]*4 for _ in range(Q)]

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

l = [i for i in range(1, M+1)]
A_list = list(itertools.combinations_with_replacement(l, N))
print(calc(A_list))

Submission status: Accepted

Solution code:
N,M,Q = list(map(int, input().split()))
C = []
for i in range(Q):
    C.append(list(map(int, input().split())))
    
import itertools
res = 0
ls=list(range(1,M+1))
for a in itertools.combinations_with_replacement(ls, N):
    p = 0
    for c in C:
        if a[c[1]-1]-a[c[0]-1]==c[2]:
            p += c[3]
        res = max(res,p)
print(res)

Submission status: Accepted

Solution code:
import itertools

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

ans = 0
for A in itertools.combinations_with_replacement(range(1, M+1), N):
    tmp = 0
    for q in queue:
        if A[q[1]-1] - A[q[0]-1] == q[2]:
            tmp += q[3]
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

d=deque([[1]])
for i in range(n):
    for j in range(len(d)):
        tmp=d.popleft()
        for k in range(m-tmp[-1]+1):
            d.append(tmp+[tmp[-1]+k])

ans=0
# print(d)
# print(type(d))
for i in range(len(d)):
    tmp=0
    lst=d[i]
    for j in range(q):
        a,b,c,e=abcd[j]
        if lst[b-1]-lst[a-1]==c:
            tmp+=e
    ans=max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
import itertools

N, M, Q = map(int, input().split())
x1 = [0]*Q
x2 = [0]*Q
x3 = [0]*Q
x4 = [0]*Q

for i in range(Q):
    x1[i], x2[i], x3[i], x4[i] = map(int, input().split())
score = 0
tmp = 0
lis = range(1, M+1)
A = []

for i in itertools.combinations_with_replacement(lis, N):
    A.append(list(i))

for i in range(len(A)):
  for j in range(Q):
    if(A[i][x2[j]-1] - A[i][x1[j]-1] == x3[j]): tmp += x4[j]
  if(tmp>=score): score = tmp
  tmp = 0

print(score)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    def dfs(aa):
        if len(aa)==n+1:
            res=0
            for a,b,c,d in ad:
                if aa[b]-aa[a]==c:res+=d
            return res

        res=-1
        for a in range(aa[-1],m+1):
            res=max(dfs(aa+[a]),res)
        return res

    n,m,q=MI()
    ad=LLI(q)
    print(dfs([1]))

main()

Submission status: Accepted

Solution code:
import sys
import math
from collections import Counter
import itertools
import fractions
#from functools import reduce

# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SR(): return sys.stdin.readline().rstrip()

ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_uppercase2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'

# リストを改行区切りで出力する
p2D = lambda x: print(*x, sep="\n")
p2E = lambda x: print(''.join(x))
p2S = lambda x: print(*x, sep=" ")

# ###########################################
 
N,M,Q=MI()
a=LLI(Q)
x=[0]*M
for i in range(1,M+1):
    x[i-1]=i
A=itertools.combinations_with_replacement(x,N)

ma=0
for z in A:
    su = 0
    for c in a:
        if z[c[1]-1] - z[c[0]-1] == c[2]:
            su += c[3]
    ma=max(ma,su)
print(ma)

Submission status: Accepted

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

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

def judge(l):
    ans=0
    for i in range(q):
        a,b,c,d=t[i]
        if l[b]-l[a]==c:
            ans+=d
    return ans

num=[]
ans=0
for i in range(1,m+1):
    num.append(i)

for df in itertools.combinations_with_replacement(num,n):

    ty=list(df)
    f=judge(ty)
    ans=max(ans,f)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

l = range(1,m+1)
point = 0
for v in itertools.combinations_with_replacement(l,n):
    p = 0
    for a,b,c,d in abcd:
        if v[b-1] - v[a-1] == c:
            p += d
    if p > point: point = p
print(point)

Submission status: Accepted

Solution code:


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

from itertools import combinations_with_replacement
AA = combinations_with_replacement(list(range(1,M+1)),N)
ans = 0
for A in AA:
    now = 0
    for q in range(Q):
        a,b,c,d = C[q]
        if A[b-1]-A[a-1]==c:
            now += d
    ans = max(ans,now)
print(ans)

Submission status: Accepted

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

    b = []
    for i in range(m):
        b.append(i + 1)

    A = list(combinations_with_replacement(b, n))

    ans = 0
    for Ai in A:
        tmp = 0
        for a, b, c, d in li:
            a -= 1
            b -= 1
            if Ai[b] - Ai[a] == c:
                tmp += d

        ans = max(ans, tmp)
    print(ans)
    
resolve()

Submission status: Accepted

Solution code:
import itertools
import numpy
N, M, Q = map(int,input().split())
abcd = []*Q
d_list = []
sum_d = 0
for _ in range(Q):
  abcd.append(list(map(int,input().split())))

A = [1 for i in range(N)]
for A in itertools.combinations_with_replacement(range(1, M+1), N):
  for i in range(Q):
    if A[abcd[i][1]-1]-A[abcd[i][0]-1] == abcd[i][2]:
      d_list.append(abcd[i][3])
  if sum_d <= sum(d_list):
    sum_d = sum(d_list)
  d_list.clear()
print(sum_d)

Submission status: Accepted

Solution code:
import itertools


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

a = [None] * Q
b = [None] * Q
c = [None] * Q
d = [None] * Q

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

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

max_v = 0
for v in itertools.combinations_with_replacement(A, N):
    tmp_sum = 0
    for i in range(Q):
        if v[b[i]] - v[a[i]] == c[i]:
            tmp_sum += d[i]
    max_v = max(max_v, tmp_sum)

print(max_v)

Submission status: Accepted

Solution code:
import itertools

N,M,Q = map(int,input().split())
num = [[0 for i in range(4)] for j in range(Q)]
test = list()

k = 1
for i in range(M):
    test.append(k)
    k += 1

k = 0
for i in range(Q):
    num[k][0], num[k][1], num[k][2], num[k][3] = map(int,input().split())
    k += 1

k = 0
score = 0
maxscore = 0
for list in itertools.combinations_with_replacement(test, N):
    for i in range(Q):
        if list[num[k][1]-1] - list[num[k][0]-1] == num[k][2]:
            score += num[k][3]
        k += 1
        if score > maxscore:
            maxscore = score
    score = 0
    k = 0

print(maxscore)

Submission status: Accepted

Solution code:
import sys
import os
from itertools import combinations_with_replacement

def file_input():
    f = open('../Beginner_Contest_165/input.txt', 'r')
    sys.stdin = f

def main():
   # file_input()
    # input()
    N,M,Q=map(int, input().split())
    Q_set=[list(map(int, input().split())) for _ in range(Q)]

    ans=0

    for A in list(combinations_with_replacement(range(1,M+1),N)):
        # print(A)
        score=0
        for Q in Q_set:
            if A[Q[1]-1]-A[Q[0]-1]==Q[2]:
                score+=Q[3]
        if ans<score:
            ans=score

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools
s=list(map(int,input().split()))
t=[list(map(int,input().split())) for i in range(s[2])]
li=[x for x in range(1,s[1]+1)]
lity=list(itertools.combinations_with_replacement(li,s[0]))
ans=0
for k in lity:
  vmax=0
  for l in t:
    if k[l[1]-1]-k[l[0]-1]==l[2]:
      vmax+=l[3]
  ans=max(ans,vmax)
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)]
ans = 0
for x in combinations_with_replacement(range(1, M+1), N):
    point = 0
    for a, b, c, d in abcd:
        if x[b-1] - x[a-1] == c:
            point += d
    if ans < point:
        ans = point
print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M,Q = map(int, input().split())
qs = []
for i in range(Q):
  qs.append(list(map(int, input().split())))
ans = 0
a = [i for i in range(1,M+1)]
cands = itertools.combinations_with_replacement(a,N)    
for cand in cands:
  _cand = [1]
  _cand.extend(cand)
  tmp = 0
  for q in qs:
    if _cand[q[1]-1]-_cand[q[0]-1] == q[2]:
      tmp += q[3]
  ans = max(ans, tmp)
print(ans)

Submission status: Accepted

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


for l in itertools.combinations_with_replacement(list_NUM, n):
    cnt = 0
    for h in list_score:
        if l[h[1]-1] - l[h[0]-1] == h[2]:
            cnt += h[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())
abcd=[list(map(int,input().split())) for i in range(q)]
ans=0
for A in combinations_with_replacement(range(m),n):
  p=0
  for i in range(q):
    a,b,c,d=abcd[i]
    if A[b-1]-A[a-1]==c:
      p+=d
  ans=max(ans,p)
print(ans)

Submission status: Accepted

Solution code:
import itertools
n, m, q = [int(a) for a in input().split()]
a = []
b = []
c = []
d = []
for i in range(q):
    a_,b_,c_,d_ = [int(a) for a in input().split()]
    a.append(a_-1)
    b.append(b_-1)
    c.append(c_)
    d.append(d_)
ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

maxs = 0
for xi in x:
    xii = list(xi)
    
    score = 0
    for ai, bi, ci, di in a:
        if xii[bi-1] - xii[ai-1] == ci:
            score += di
    maxs = max(maxs, score)
print(maxs)

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

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

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

########関数部分##############
def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)
############################
 
n,m,q = myinput()
abcd = mylistinput(q)

ls = list( combinations_with_replacement(list(range(1,m+1)),n) )
# print(len(ls))
# pprint(ls)

ls_ans = []
for i in range(len(ls)):
    A = list(ls[i])
    # print(A)
    score = 0
    for j in range(q):
        a = abcd[j][0] - 1
        b = abcd[j][1] - 1
        c = abcd[j][2]
        d = abcd[j][3]
        if A[b]-A[a]==c:
            score += d
        else:
            pass
    ls_ans.append(score)
# print(ls_ans)
ans = max(ls_ans)
print(ans)

Submission status: Accepted

Solution code:
def dfs(A, max_a):
    if len(A) == n:
        score = 0
        for a, b, c, d in conditions:
            if A[b - 1] - A[a - 1] == c:
                score += d
        return score
    ans = 0
    for i in range(max_a, m + 1):
        ans = max(ans, dfs(A + [i], i))
    return ans


n, m, q = map(int, input().split())
conditions = [list(map(int, input().split())) for _ in range(q)]
print(dfs([1], 1))

Submission status: Accepted

Solution code:
import sys
import itertools


sys.setrecursionlimit(10 ** 7)

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

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


def calsScore(lst):
    s = 0
    for a, b, c, d in ABCD:
        if (lst[b - 1] - lst[a - 1]) == c:
            s += d
    return s


import copy


def dfs(i, lst, N):
    ans = 0
    lst.append(i)
    N -= 1

    if N == 0:
        return calsScore(lst)
    else:
        for j in range(i, M + 1):
            nlst = copy.copy(lst)
            ans = max(dfs(j, nlst, N), ans)

    return ans


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

Submission status: Accepted

Solution code:
def ite(N, M):
    import itertools
    return itertools.combinations_with_replacement(range(M),N)
def check(li):
    for i in range(len(li)-1):
        if li[i] > li[i+1]:
            return False
    return True
    
def score(l1, l2):
    s = 0
    for (a, b, c, d) in l2:
      if l1[b-1] - l1[a-1] == c:
            s += d
    return s
        

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

m_s = 0
for l2 in ite(N, M):
    s = score(l2, li)
    if m_s < s:
      m_s = s
            
print(m_s)

Submission status: Accepted

Solution code:

import math
import itertools

def solve(N:int,M:int,Q:int,ABCD:list) -> int:
    ans = 0
    elements = [i for i in range(1,M+1)] # 数列Aにあり得る要素
    # 条件を満たす数列Aを作成
    for A in itertools.combinations_with_replacement(elements,N):
        total = 0 # 現在の数列の得点を格納する変数
        for a,b,c,d in ABCD:
            if(A[b-1] - A [a-1] == c): # 条件を満たしていたら得点を追加
                total+=d
        ans = max(ans,total) # 最高得点を更新
    return ans



def main():
    N ,M,Q = map(int,input().split())
    ABCD = []
    for _ in range(Q):
        ABCD.append(list(map(int,input().split())))
    # solve()
    print(solve(N,M,Q,ABCD))
if __name__ == '__main__':
   main()

Submission status: Accepted

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

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

cand = [[1]]
for i in range(N-1):
    tmp = []
    while cand:
        x = cand.pop()
        for i in range(x[-1], M + 1):
            tmp.append(x + [i])
    cand = tmp

ans = 0
for X in cand:
    score = 0
    for a, b, c, d in abcd:
        if X[b - 1] - X[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())
a = []
b = []
c = []
d = []
for _ in range(q):
    ai, bi, ci, di = map(int, input().split())
    a.append(ai)
    b.append(bi)
    c.append(ci)
    d.append(di)

num = list(range(1, m + 1))
max_score = 0
for A in list(combinations_with_replacement(num, n)):
    score = 0
    for i in range(q):
        if A[b[i] - 1] - A[a[i] - 1] == c[i]:
            score += d[i]
    max_score = max(max_score, score)
print(max_score)

Submission status: Accepted

Solution code:
import itertools

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

numbers = []
for i in range(Q):
    numbers.append([int(j) for j in input().split()])


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

answer = 0
for k in  A:
    ans = 0
    for a, b, c, d in numbers:
        if int(k[b-1]) - int(k[a-1]) == c:
            ans += d
    if answer < ans:
        answer = ans
print(answer)

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

ans = 0
for v in combinations_with_replacement(range(1, M+1), N):
    A = list(v)
    temp = 0
    for a, b, c, d in abcd:
        if A[b-1] - A[a-1] == c:
            temp += d
    ans = max(ans, temp)

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

answer = []
for i in range(len(Alist)):
    score = 0
    for j in range(q):
        b = li[j][1]-1
        a = li[j][0]-1
        if (Alist[i][b] - Alist[i][a] == li[j][2]):
            score += li[j][3]
    answer.append(score)

print(max(answer))

Submission status: Accepted

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

def calculate(A):
    total = 0
    for abcdi in abcd:
        a = abcdi[0] - 1
        b = abcdi[1] - 1
        c = abcdi[2]
        d = abcdi[3]
        if A[b] - A[a] == c:
            total += d
    # print(A, total)

    return total

maximum = 0
for i in range(1, M + 1):
    if N == 1:
        maximum = max(calculate([i]), maximum)
    for j in range(i, M + 1):
        if N == 2:
            maximum = max(calculate([i, j]), maximum)
        for k in range(j, M + 1):
            if N == 3:
                maximum = max(calculate([i, j, k]), maximum)
            for l in range(k, M + 1):
                if N == 4:
                    maximum = max(calculate([i, j, k, l]), maximum)
                for m in range(l, M + 1):
                    if N == 5:
                        maximum = max(calculate([i, j, k, l, m]), maximum)
                    for n in range(m, M + 1):
                        if N == 6:
                            maximum = max(calculate([i, j, k, l, m, n]), maximum)
                        for o in range(n, M + 1):
                            if N == 7:
                                maximum = max(calculate([i, j, k, l, m, n, o]), maximum)
                            for p in range(o, M + 1):
                                if N == 8:
                                    maximum = max(calculate([i, j, k, l, m, n, o, p]), maximum)
                                for q in range(p, M + 1):
                                    if N == 9:
                                        maximum = max(calculate([i, j, k, l, m, n, o, p, q]), maximum)
                                    for r in range(q, M + 1):
                                        if N == 10:
                                            maximum = max(calculate([i, j, k, l, m, n, o, p, q, r]), maximum)

print(maximum)

Submission status: Accepted

Solution code:
def main():
    n,m,q = map(int,input().split())
    a = [list(map(int, input().split())) for _ in range(q)]
    #a = sorted(a, key=lambda x:-x[3])
    ans = 0
    from itertools import combinations_with_replacement
    for dp in combinations_with_replacement(range(1,m+1),n):
        res = 0
        for j in range(q):
            if dp[a[j][1]-1] - dp[a[j][0]-1] == a[j][2]:
                res += a[j][3]
        ans = max(res,ans)
    print(ans)
    
if __name__ == '__main__':
    main()