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:
N, M, Q = list(map(int,input().split()))
conditions = [list(map(int,input().split())) for q in range(Q)]

def make_list(len_, max_, list_):
    min_ = list_[-1]
    lists = [list_ + [i] for i in range(min_, max_+1)]
    if len(list_)+1 == len_:
        return lists
    else:
        return_lists = []
        for l in lists:
            return_lists += make_list(len_, max_, l)
        return return_lists

all_lists = []
for j in range(1, M+1):
    all_lists += make_list(N, M, [j])

points = []
for A in all_lists:
    point = 0
    for a,b,c,d in conditions:
        if A[b-1]-A[a-1]==c:
            point += d
    points.append(point)
    
print(max(points))

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement


n, m, q = map(int, input().split())
cl = []
dl = []
abl = []

for _ in range(q):
    a, b, c, d = map(int, input().split())
    cl.append(c)
    dl.append(d)
    abl.append([a, b])

ans = 0
for comb in list(combinations_with_replacement(range(1, m+1), n)):
    point = 0
    for i, ab in enumerate(abl):
        a, b = ab
        if comb[b-1] - comb[a-1] == cl[i]:
            point += dl[i]
    ans = max(ans, point)
print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M,Q = (int(x) for x in input().split())
l = []
ABCD = []
for i in range(1,M+1):
  l.append(i)
A = list(itertools.combinations_with_replacement(l, N))
for j in range(Q):
    a,b,c,d = (int(x) for x in input().split())
    ABCD.append((a,b,c,d))
max = 0
for i in range(len(A)):
  cnt = 0
  for j in range(Q):
    a = ABCD[j][0]
    b = ABCD[j][1]
    if A[i][b-1]-A[i][a-1] == ABCD[j][2]:
      cnt += ABCD[j][3]
     # print(A[i],ABCD[j],cnt,max)
  if max < cnt:
     max = cnt
print(max)

Submission status: Accepted

Solution code:
def main():
  from sys import stdin
  import itertools
  N, M, Q = map(int, input().split())
  scores = [list(map(int, stdin.readline().split())) for _ in range(Q)]
  best = 0
  x = list(range(1, M+1))
  for y in itertools.combinations_with_replacement(x, N):
    target = sorted(list(y))
    sco = 0
    for score in scores:
      if target[score[1]-1] - target[score[0]-1] == score[2]:
      	sco += score[3]
    if sco > best:
      best = sco
      
  print(best)
main()

Submission status: Accepted

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

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

max_point = 0
point_cont = 0
for pt in comb:
    point_cont = 0
    for list_pt in List:
        if pt[list_pt[1]-1] - pt[list_pt[0]-1] == list_pt[2]:
            point_cont += list_pt[3]
    if max_point <= point_cont:
        max_point = point_cont

print(max_point)

Submission status: Accepted

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

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

# 数列の作成
import itertools
combs = list(itertools.combinations_with_replacement(list(range(1, m+1)), n))

ans = 0
for comb in combs:
  point = 0
 
  for abcd in abcds:
    if (int(comb[abcd[1]-1])-int(comb[abcd[0]-1]) == abcd[2]):
      point += abcd[3]
  ans = max(ans, point)
 
print(ans)

Submission status: Accepted

Solution code:
n,m,q = map(int ,input().split())
lst = [list(map(int, input().split())) for _ in range(q)]
import itertools
l = [i+1 for i in range(m)]
lst2 = [com for com in itertools.combinations_with_replacement(l, n)]
res = 0
for com in lst2:
    score = 0
    for l in lst:
        if com[l[1]-1] - com[l[0]-1] == l[2]:
            score += l[3]
    if res < score:
        res = score 
    #print(score)
print(res)

Submission status: Accepted

Solution code:
import itertools
n,m,q=map(int,input().split())
p=[list(map(int,input().split())) for i in range(q)]
ans=0
def init(n):
  c=[i for i in range(1,m+1)]
  cand=[]
  for i in c:
    cand.append([i])
  for _ in range(n-1):
    cand2=[]
    for i in range(len(cand)):
      for j in range(cand[i][-1],m+1):
        cand2.append(cand[i]+[j])
    cand=cand2
  return cand
cand=init(n)
for i in range(len(cand)):
  m=0
  for j in range(q):
    if cand[i][p[j][1]-1]-cand[i][p[j][0]-1]==p[j][2]:
      m+=p[j][3]
  if m>ans:
    ans=m
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

for A in combinations_with_replacement(range(1,M+1),N):
    tensu=0
    for abcd_i in abcd:
        ai=abcd_i[0]
        bi=abcd_i[1]
        ci=abcd_i[2]
        di=abcd_i[3]

        if A[bi-1]-A[ai-1]==ci:
            tensu+=di
        
    ans=max(ans,tensu)

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

def A_score(A):
    dsum = 0
    for i in range(q):
        a, b, c, d = abcd[i]
        if A[b-1] - A[a-1] == c:
            dsum += d
    return dsum

seq = [i for i in range(1,m+1)]
A_comb = list(itertools.combinations_with_replacement(seq, n))
ans = 0

for t in A_comb:
    score = A_score(t)
    if  score > ans:
        ans = score

print(ans)

Submission status: Accepted

Solution code:
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

N, M, Q = MAP()
req = []
for i in range(Q):
    a, b, c, d = MAP()
    req.append([a-1, b-1, c, d])

A = [[1]*N, ]
def plus(a):
    n = len(a)
    if a[n-1] !=M:
        a[n-1] = a[n-1]+1
        return a
    if n==1: return [M,]
    res = plus(a[:n-1])
    return res + [res[n-2],]

while True:
    a = A[-1]
    if a == [M]*N:
        break
    A.append(plus(a))

res = 0
for i in range(len(A)):
    temp = 0
    for j in range(Q):
        if A[i][req[j][1]] - A[i][req[j][0]] == req[j][2]:
            temp += req[j][3]
    if temp > res:
        res = temp

print(res)

Submission status: Accepted

Solution code:
import itertools

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

ans = 0

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

for v in itertools.combinations_with_replacement(l, n):
  v = sorted(list(v))
  now = 0
  for i in range(q):
    a, b, c, d = query[i]
    if v[b-1] - v[a-1] == c:
      now += d
  ans = max(ans, now)
  
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M, Q = lr()
ABCD = [lr() for _ in range(Q)]
A = [1] * N
ABCD.sort(key=lambda x: x[3], reverse=True)
ABCD.sort(key=lambda x: x[0])
answer = 0
for a in [1]:
    for b in range(a, M+1):
        for c in range(b, M+1):
            for d in range(c, M+1):
                for e in range(d, M+1):
                    for f in range(e, M+1):
                        for g in range(f, M+1):
                            for h in range(g, M+1):
                                for i in range(h, M+1):
                                    for j in range(i, M+1):
                                        temp = 0
                                        x = [a,b,c,d,e,f,g,h,i,j]
                                        for k, l, m, n in ABCD:
                                            if x[l-1] - x[k-1] == m:
                                                temp += n
                                        if temp > answer:
                                            answer = temp

print(answer)

Submission status: Accepted

Solution code:
import itertools

s1 = input()

N = int(s1.split()[0])
M = int(s1.split()[1])
Q = int(s1.split()[2])

a = []
b = []
c = []
d = []

s = [input() for i in range(Q)]

for k in range(Q):
  a.append(int(s[k].split()[0]))
  b.append(int(s[k].split()[1]))
  c.append(int(s[k].split()[2]))
  d.append(int(s[k].split()[3]))
  
result = 0
  
suretu = []
for i in range(M):
  suretu.append(i+1)
  
for A in list(itertools.combinations_with_replacement(suretu, N)):
  A = list(A)
  subresult = 0
  for i in range(Q):
    if A[b[i]-1] - A[a[i]-1] == c[i]:
      subresult += d[i]
  if result < subresult:
    result = subresult
    
print(result)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache

import heapq


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N,M,Q = inputIL()
A = inputILL(Q)

l = []
count = 0
for i_1 in range(1,M+1):
  for i_2 in range(i_1,M+1):
    for i_3 in range(i_2,M+1):
      for i_4 in range(i_3,M+1):
        for i_5 in range(i_4,M+1):
          for i_6 in range(i_5,M+1):
            for i_7 in range(i_6,M+1):
              for i_8 in range(i_7,M+1):
                for i_9 in range(i_8,M+1):
                  for i_10 in range(i_9,M+1):
                    l.append([i_1,i_2,i_3,i_4,i_5,i_6,i_7,i_8,i_9,i_10])
                    

best = 0 
for item in l:
  score = 0
  for q in A:
    a,b,c,d = q
    if item[b-1] - item[a-1] == c:
      score += d
  best = max(score,best)
  
print(best)

Submission status: Accepted

Solution code:
import itertools
n, m, q = map(int, input().split())
v = []
for i in range(q):
    a, b, c, d = map(int, input().split())
    a -= 1
    b -= 1
    v.append(list([a, b, c, d]))

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

Submission status: Accepted

Solution code:
#N, M, Qの制約がしょぼいので、総当たりで計算する。O(MCN)で済む。
import itertools
N, M, Q = map(int, input().split())
point = []
for i in range(Q):
    a = list(map(int, input().split()))
    point.append(a)
#まず1 ~ MからNコ選んだ数列をすべて作る。
all = list(itertools.combinations_with_replacement([i + 1 for i in range(M)], N - 1))
ans = []
m = 0
for i in all:
    now = [1]
    now += list(i)
    p = 0
#    print("i", now)
    for j in point:
#        print("j", j)
        a, b, c, d = j[0], j[1], j[2], j[3]
        if now[b - 1] - now[a - 1] == c:
            p += d
    if p > m:
#        print(p, i)
        m = p
        ans = now
print(m)

Submission status: Accepted

Solution code:
import itertools

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

kazu = []

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

ans = 0

for v in itertools.combinations_with_replacement(kazu, n):
    memo = 0
    for i , j ,k ,l in ab:
        if v[j-1]-v[i-1] == k:
            memo += l
    ans = max(memo,ans)
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)]

points = []
for able in itertools.combinations_with_replacement(range(1, m+1), n):
    point = 0
    for a, b, c, d in abcd:
        if able[b-1] - able[a-1] == c:
            point += d
    points.append(point)

print(max(points))

Submission status: Accepted

Solution code:

def check(l,P):
    f = 0
    for i in P:
        if l[i[1]-1] - l[i[0]-1] == i[2]:
            f += i[3]
    return f
def main():
    A,B,C = map(int,input().split())
    P = [list(map(int,input().split())) for i in range(C)]
    L = [[1]]
    for i in range(2,A+1):
        L2 = []
        for j in L:
            for k in range(j[-1],B+1):
                L2.append(j+[k])
        L = L2[:]
    res = 0
    for i in L:
        res = max(res,check(i,P))
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans =0
    
if n == 2:
    for a in range(1, m+1):
        for b in range(a, m+1):
            A = [a, b]
            ans_ = 0
            for res in abcd:
                if A[res[1]] - A[res[0]] == res[2]: ans_ += res[3]
            ans = max(ans, ans_)   
            
elif n == 3:
    for a in range(1, m+1):
        for b in range(a, m+1):
            for c in range(b, m+1):
                A = [a, b, c]
                ans_ = 0
                for res in abcd:
                    if A[res[1]] - A[res[0]] == res[2]: ans_ += res[3]
                ans = max(ans, ans_)      
                
elif n == 4:
    for a in range(1, m+1):
        for b in range(a, m+1):
            for c in range(b, m+1):
                for d in range(c, m+1):
                    A = [a, b, c, d]
                    ans_ = 0
                    for res in abcd:
                        if A[res[1]] - A[res[0]] == res[2]: ans_ += res[3]
                    ans = max(ans, ans_)
                    
elif n == 5:
    for a in range(1, m+1):
        for b in range(a, m+1):
            for c in range(b, m+1):
                for d in range(c, m+1):
                    for e in range(d, m+1):
                        A = [a, b, c, d, e]
                        ans_ = 0
                        for res in abcd:
                            if A[res[1]] - A[res[0]] == res[2]: ans_ += res[3]
                        ans = max(ans, ans_)
                        
elif n == 6:
    for a in range(1, m+1):
        for b in range(a, m+1):
            for c in range(b, m+1):
                for d in range(c, m+1):
                    for e in range(d, m+1):
                        for f in range(e, m+1):
                            A = [a, b, c, d, e, f]
                            ans_ = 0
                            for res in abcd:
                                if A[res[1]] - A[res[0]] == res[2]: ans_ += res[3]
                            ans = max(ans, ans_)
                            
elif n == 7:
    for a in range(1, m+1):
        for b in range(a, m+1):
            for c in range(b, m+1):
                for d in range(c, m+1):
                    for e in range(d, m+1):
                        for f in range(e, m+1):
                            for g in range(f, m+1):
                                A = [a, b, c, d, e, f, g]
                                ans_ = 0
                                for res in abcd:
                                    if A[res[1]] - A[res[0]] == res[2]: ans_ += res[3]
                                ans = max(ans, ans_)
                                
elif n == 8:
    for a in range(1, m+1):
        for b in range(a, m+1):
            for c in range(b, m+1):
                for d in range(c, m+1):
                    for e in range(d, m+1):
                        for f in range(e, m+1):
                            for g in range(f, m+1):
                                for h in range(g, m+1):
                                    A = [a, b, c, d, e, f, g, h]
                                    ans_ = 0
                                    for res in abcd:
                                        if A[res[1]] - A[res[0]] == res[2]: ans_ += res[3]
                                    ans = max(ans, ans_)
                                    
elif n == 9:
    for a in range(1, m+1):
        for b in range(a, m+1):
            for c in range(b, m+1):
                for d in range(c, m+1):
                    for e in range(d, m+1):
                        for f in range(e, m+1):
                            for g in range(f, m+1):
                                for h in range(g, m+1):
                                    for i in range(h, m+1):
                                        A = [a, b, c, d, e, f, g, h, i]
                                        ans_ = 0
                                        for res in abcd:
                                            if A[res[1]] - A[res[0]] == res[2]: ans_ += res[3]
                                        ans = max(ans, ans_)
                
elif n == 10:
    for a in range(1, m+1):
        for b in range(a, m+1):
            for c in range(b, m+1):
                for d in range(c, m+1):
                    for e in range(d, m+1):
                        for f in range(e, m+1):
                            for g in range(f, m+1):
                                for h in range(g, m+1):
                                    for i in range(h, m+1):
                                        for j in range(i, m+1):
                                            A = [a, b, c, d, e, f, g, h, i, j]
                                            ans_ = 0
                                            for res in abcd:
                                                if A[res[1]] - A[res[0]] == res[2]: ans_ += res[3]
                                            ans = max(ans, ans_)
                                                    
print(ans)

Submission status: Accepted

Solution code:
import math
#X=int(input())
N,M,Q=map(int,input().split())
S=[[]for i in range(Q)]
for i in range(Q):
    a=list(map(int,input().split()))
    S[i]=a
ans=0
T=0
for a in range(1,M+1):
    for b in range(a, M+1):
        for c in range(b, M+1):
            for d in range(c, M+1):
                for e in range(d, M+1):
                    for f in range(e, M+1):
                        for g in range(f, M+1):
                            for h in range(g, M+1):
                                for i in range(h, M+1):
                                    for j in range(i, M+1):
                                        D=[a,b,c,d,e,f,g,h,i,j]
                                        for k in range(Q):
                                            if D[S[k][1]-1]-D[S[k][0]-1]==S[k][2]:
                                                ans+=S[k][3]
                                        if ans>=T:
                                            T=ans
                                        ans = 0
print(T)

Submission status: Accepted

Solution code:
n,m,q = [int(x) for x in input().split()]
li = []
for i in range(q):
    li.append([int(x) for x in input().split()])
import itertools
num = range(1,m+1)
v = list(itertools.combinations_with_replacement(num,n))
ans = 0
for i in v:
    su = 0
    for j in li:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            su+=j[3]
    ans = max(ans,su)
print(ans)

Submission status: Accepted

Solution code:
n, M, Q = map(int, input().split())
a, b, c, d = [], [], [], []
for _ in [0]*Q:
    aa, bb, cc, dd = map(int, input().split())
    a += [aa-1]; b += [bb-1]; c += [cc]; d += [dd]
if n==2:
    AA = [[i, j] for i in range(1, M+1) for j in range(i, M+1)]
elif n==3:
    AA = [[i, j, k] for i in range(1, M+1) for j in range(i, M+1) for k in range(j, M+1)]
elif n==4:
    AA = [[i, j, k, l] for i in range(1, M+1) for j in range(i, M+1) for k in range(j, M+1) for l in range(k, M+1)]
elif n==5:
    AA = [[i, j, k, l, m] for i in range(1, M+1) for j in range(i, M+1) for k in range(j, M+1) for l in range(k, M+1) for m in range(l, M+1)]
elif n==6:
    AA = [[i, j, k, l, m, n] for i in range(1, M+1) for j in range(i, M+1) for k in range(j, M+1) for l in range(k, M+1) for m in range(l, M+1) for n in range(m, M+1)]
elif n==7:
    AA = [[i, j, k, l, m, n, o] for i in range(1, M+1) for j in range(i, M+1) for k in range(j, M+1) for l in range(k, M+1) for m in range(l, M+1) for n in range(m, M+1) for o in range(n, M+1)]
elif n==8:
    AA = [[i, j, k, l, m, n, o, p] for i in range(1, M+1) for j in range(i, M+1) for k in range(j, M+1) for l in range(k, M+1) for m in range(l, M+1) for n in range(m, M+1) for o in range(n, M+1) for p in range(o, M+1)]
elif n==9:
    AA = [[i, j, k, l, m, n, o, p, q] for i in range(1, M+1) for j in range(i, M+1) for k in range(j, M+1) for l in range(k, M+1) for m in range(l, M+1) for n in range(m, M+1) for o in range(n, M+1) for p in range(o, M+1) for q in range(p, M+1)]
elif n==10:
    AA = [[i, j, k, l, m, n, o, p, q, r] for i in range(1, M+1) for j in range(i, M+1) for k in range(j, M+1) for l in range(k, M+1) for m in range(l, M+1) for n in range(m, M+1) for o in range(n, M+1) for p in range(o, M+1) for q in range(p, M+1) for r in range(q, M+1)]
ans = 0
for A in AA:
    tmp = 0
    for i in range(Q):
        if A[b[i]] - A[a[i]] == c[i]:
            tmp += d[i]
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
import itertools


N, M, Q = map(int, input().split())
nums_list = []
A = [] # 最大M
for m in range(M):
    A.append(m+1)
run_list = []
for v in itertools.combinations_with_replacement(A, N):
    count = 0 
    for i in range(N-1):
        if v[i] <= v[i+1]:
            count += 1
    if count == N-1:
        run_list.append(v)

for q in range(Q):
    nums = [int(x.strip()) for x in input().split(' ') ]
    nums_list.append(nums)
ans = 0

for run in run_list:
    tmp = 0
    for num in nums_list:
        if run[num[1]-1] - run[num[0]-1] == num[2]:
            tmp = tmp + num[3]
            
    if ans < tmp:
        ans = tmp
    
print(ans)

Submission status: Accepted

Solution code:
N, M, Q = list(map(int, input().split()))
A, B, C, D = [], [], [], []
for _ in range(Q):
    a, b, c, d = list(map(int, input().split()))
    A.append(a-1)
    B.append(b-1)
    C.append(c)
    D.append(d)
    
arrays = []
def backtrack(l, N, M, cur):
    if len(cur) == N:
        arrays.append(cur[:])
    else:
        for num in range(l, M+1):
            cur.append(num)
            backtrack(num, N, M, cur)
            cur.pop()
backtrack(1, N, M, [])

ans = 0
for arr in arrays:
    tmp = 0
    for i in range(Q):
        a, b, c, d = A[i], B[i], C[i], D[i]
        if arr[b] - arr[a] == c:
            tmp += d
    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
n,m,q = list(map(int, input().split(' ')))
list1 = []
for i in range(q):
    list1.append(list(map(int, input().split(' '))))
def calc(a):
    global list1
    tot = 0
    for l in list1:
        if a[l[1]-1]-a[l[0]-1]==l[2]:
            tot += l[3]
    return tot

max1 = -1
def dfs(a=[]):
    global max1,n,m,q
    if(len(a)==n):
        c = calc(a)
        if c>max1:
            max1 = c
    else:
        start = a[-1] if a else 0
        for i in range(start, m):
            a.append(i)
            dfs(a)
            a.pop(-1)
dfs()
print(max1)

Submission status: Accepted

Solution code:
import itertools

N, M, Q = map(int, input().split())
ABCD = []
for _ in range(Q):
    ABCD.append(list(map(int, input().split())))
M_list = [i+1 for i in range(M)]
N_list = itertools.combinations_with_replacement(M_list, N)
max_point = 0
for n in N_list:
    point = 0
    for abcd in ABCD:
        if n[abcd[1]-1] - n[abcd[0]-1] == abcd[2]:
            point += abcd[3]
    if max_point < point:
        max_point = point
print(max_point)

Submission status: Accepted

Solution code:

import heapq
from collections import defaultdict, deque
from math import ceil, factorial, gcd
from itertools import accumulate, permutations
import sys
import bisect

sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
msi = lambda: map(str, input().split())
lmii = lambda: list(map(int, input().split()))
lmsi = lambda: list(map(str, input().split()))
smii = lambda: sorted(map(int, input().split()))

# ----------

N, M, Q = mii()

ans = 0

ABCD = []
for i in range(Q):
    a, b, c, d = mii()
    ABCD.append([a-1, b-1, c, d])

def calc(arr):
    ret = 0
    for a, b, c, d in ABCD:
        if arr[b] - arr[a] == c:
            ret += d
    return ret

def dfs(length, n, arr):
    global ans
    if length == N:
        ans = max(ans, calc(arr))
        return
    for i in range(n, M+1):
        arr.append(i)
        dfs(length+1, i, arr)
        arr.pop(-1)


dfs(0, 1, [])

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

n, m, q = list(map(int,input().split()))
A = [list(map(int,input().split())) for i in range(q)]
def keisan(tup):
    ans_keisan = 0
    for j in A:
        if tup[j[1]-1] - tup[j[0]-1] == j[2]:
            ans_keisan += j[3]
    return ans_keisan
ans = 0
for i in combinations_with_replacement(range(m),n):
    ans = max(keisan(i), ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
input = lambda:sys.stdin.readline().strip()
n,m,q = map(int,input().split())
score = 0
def calc_score(arr):
    val = 0
    for i in qs:
        a,b,c,d = i 
        if arr[b-1]-arr[a-1]==c:
            val+=d
    return val
def f(i,ne,arr):
    if i==n:
        global score 
        score = max(score,calc_score(arr))
        return 
    for j in range(ne,m+1):
        arr = arr+[j]
        f(i+1,j,arr)
        arr.pop()
qs = []
for i in range(q):
    qs.append(list(map(int,input().split())))
f(0,1,[])
print(score)

Submission status: Accepted

Solution code:
import itertools
N, M, Q = input().split()
N = int(N)
M = int(M)
Q = int(Q)
Num = [0 for i in range(Q)]
for i in range(Q):
  Num[i] = list(map(int,input().split()))
num = list(range(1, M+1))
A = []
for v in itertools.combinations_with_replacement(num, N):
  A.append(list(v))
score = 0
for w in A:
  scoreX = 0
  for j in range(Q):
    b = Num[j][1]
    a = Num[j][0]
    if Num[j][2] == w[b-1]-w[a-1]:
      scoreX += Num[j][3]
  if scoreX > score:
    score = scoreX
print(str(score))

Submission status: Accepted

Solution code:
import itertools

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

def solve(N, M, constraints):
    max_so_far = 0
    for seq in itertools.combinations_with_replacement(range(1, M + 1), N):
        #print("Processing sequence: ", seq)
        curr_score = 0
        for const in constraints:
            a,b,c,d = const
            if seq[b-1] - seq[a-1] == c:
                curr_score += d

        max_so_far = max(max_so_far, curr_score)

    return max_so_far


N, M, Q = iln()
constraints = []
for i in range(Q):
    constraint = tuple(iln())
    constraints.append(constraint)

print(solve(N, M, constraints))

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(1,M+1),N):
    p = 0
    for a,b,c,d in abcd:
        if A[b-1] - A[a-1] == c:
            p += d
    ans = max(p,ans)

print(ans)

Submission status: Accepted

Solution code:
import itertools
def getAscore(A, Qlist):
    score = 0
    for l in Qlist:
        try:
            if A[l[1]-1]-A[l[0]-1] == l[2]:
                score += l[3]
        except:
            pass
    return score

NMQ = list(map(int,input().split()))
N = NMQ[0]
M = NMQ[1]
Q = NMQ[2]
Qlist = []
for n in range(Q):
    Qlist.append([int(i) for i in input().split()])
allA = list(itertools.combinations_with_replacement(range(1,M+1), N))
max = 0
for A in allA:
    score = getAscore(A, Qlist)
    if score > max:
        max = score
print(max)