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 = (int(i) for i in input().split())  
ABCD = []
ans = -1

for _ in range(Q):
  ABCD.append([int(i) for i in input().split()] )

comb_list = []

import sys
sys.setrecursionlimit(100000000)
def recur(N, lis, c):
  if len(lis) == N:
    comb_list.append(lis)
    return

  if lis == []:
    for i in range(1, M+1):
      recur(N, [i], c+1)
  else:
    for i in range(lis[c], M+1):
      recur(N, lis + [i], c+1)     

recur(N, [], -1)
for x in comb_list:
    tmp = 0
    for a, b, c, d in ABCD:
        if x[b-1] - x[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())
mylist = [list(map(int, input().split())) for i in range(q)]
#print(mylist)

kouho = []
for i in range(1, m+1):
  kouho.append(i)
#print(kouho)

A = list(itertools.combinations_with_replacement(kouho,n))
#print(A)

point = 0
maxp = 0
for a in A:
  point = 0
  #print(a)
  for my in mylist:
    #print(my)
    #print(a[my[1]-1] - a[my[0]-1])
    #print(my[2])
    #print("")
    if a[my[1]-1] - a[my[0]-1] == my[2]:
      point += my[3]
      #print("yes")
      #print(point)
  #print(point)
  if point > maxp:
    maxp = point
    #print("max更新")
    #print(maxp)
print(maxp)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

N,M,Q=map(int,input().split())
abcd = []
for i in range(Q):
    x=list(map(int,input().split()))
    abcd.append(x)
ans,cnt=0,0
aa = [i for i in range(1,M+1)]
aa = list(combinations_with_replacement(aa,N))
for x in aa:
    x = list(x)
    for i in range(Q):
        ai,bi,ci,di = abcd[i][0]-1,abcd[i][1]-1,abcd[i][2],abcd[i][3]
        if int(x[bi]) - int(x[ai]) == int(ci):
           cnt+=di
    if cnt>=ans:
        ans = cnt
        cnt=0
    else:
        cnt=0
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
inputs = open(0).readlines()
n, m, q = map(int, inputs[0].split())
ABCD = [list(map(int, x.split())) for x in inputs[1:]]

ans = 0
for x in combinations_with_replacement(range(1, m+1), n):
    e = 0
    for a, b, c, d in ABCD:
        if x[b-1] - x[a-1] == c:
            e += d
    ans = max(e, ans)
print(ans)

Submission status: Accepted

Solution code:

def get_score():
	score = 0
	for q in quads:
		a,b,c,d = q
		if arr[b] - arr[a] == c:
			score += d
	return score

def get_new_arr():
	last_update = N
	for i in reversed(range(N+1)):
		arr[i] = arr[i] + 1
		if arr[i] <= M:
			last_update = i
			break
	for i in range(last_update+1, N+1):
		arr[i] = arr[last_update]

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

quads = []
for q in range(Q):
	quads.append(map(int, raw_input().split()))

arr = [1]*(N+1)
best_score = 0
while arr != [2]*(N+1):
	score = get_score()
	if score > best_score:
		best_score = score
	get_new_arr()

print best_score

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M,Q=map(int,input().split())
g=0
lst=[[0 for e in range(4)] for f in range(Q)]
for k in range(Q):
 lst[k]=list(map(int,input().split()))
for i in range(2**(M+N)):
 E=0
 W=1
 Sui=[0]*(M+N)
 for j in range(M+N):
  if ((i >> j) & 1):
   Sui[E]=W
   E+=1
  else:
   W+=1
 if E==N and Sui[N-1]<=M:
  f=0
  for s in range(Q):
   if Sui[lst[s][1]-1]-Sui[lst[s][0]-1]==lst[s][2]:
    f+=lst[s][3]
  g=max(g,f)
print(g)

Submission status: Accepted

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

R=0
for a in range(m):
    for b in range(a,m):
        for c in range(b,m):
            for d in range(c,m):
                for e in range(d,m):
                    for f in range(e,m):
                        for g in range(f,m):
                            for h in range(g,m):
                                for i in range(h,m):
                                    for j in range(i,m):
                                        A=[a+1,b+1,c+1,d+1,e+1,f+1,g+1,h+1,i+1,j+1]
                                        r=0
                                        for k in range(q):
                                            if A[L[k][1]-1]-A[L[k][0]-1]==L[k][2]:
                                                r+=L[k][3]
                                        R=max(R,r)
print(R)

Submission status: Accepted

Solution code:
import sys
from math import sqrt
from collections import Counter, defaultdict, deque

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


def I():
    return int(input())


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


def LI():
    return list(MI())


def LIN(n: int):
    return [I() for _ in range(n)]


inf = float("inf")
mod = 10 ** 9 + 7

ma = 0


def main():
    n, m, q = MI()
    li = [LI() for _ in range(q)]

    m = m + 1
    l = [0] * n

    def f(x, now):
        global ma

        if now == n:
            s = 0
            for abcd in li:
                if l[abcd[1] - 1] - l[abcd[0] - 1] == abcd[2]:
                    s += abcd[3]
            if ma < s:
                ma = s

            return

        for i in range(x, m):
            l[now] = i
            f(i, now + 1)

    f(1, 0)

    print(ma)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

if n == 2:
  for a in range(1,m+1):
    for b in range(a, m+1):
      lst.append([a, b])
    
if n == 3:
  for a in range(1,m+1):
    for b in range(a, m+1):
      for c in range(b, m+1):
        lst.append([a, b, c])

if 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):
          lst.append([a, b, c, d])                      

if 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):
            lst.append([a, b, c, d, e])

if 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):
              lst.append([a, b, c, d, e, f])
                      
if 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):      
                lst.append([a, b, c, d, e, f, g])
                      
if 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):
                  lst.append([a, b, c, d, e, f, g, h])
                      
if 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):
                    lst.append([a, b, c, d, e, f, g, h, i])
                      
if 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):
                      lst.append([a, b, c, d, e, f, g, h, i, j])
        
ans = 0        
for i in range(len(lst)):
  res = 0
  for j in range(q):
    if lst[i][req[j][1]-1] - lst[i][req[j][0]-1] == req[j][2]:
      res += req[j][3]
  ans = max(ans, res)

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

num_list = [int(x) for x in range(1, M+1)]
pairs = []

for pair in itertools.combinations_with_replacement(num_list, N):
    pairs.append(pair)

ans = 0

# ペアを指定
for pair in pairs:
    now_sum = 0
    # そのペアでのsumを計算
    for target_row in Xn:
        #print(target_row)
        ai = target_row[0]
        bi = target_row[1]
        ci = target_row[2]
        di = target_row[3]
        # A[bi] - A[ai] - ciを計算
        if(pair[bi-1] - pair[ai-1] - ci == 0):
            now_sum = now_sum + di
    ans = max(ans, now_sum)
    #print(f"今のペア:{pair}→合計点:{now_sum}")

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

Submission status: Accepted

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

A=[]
B=[]
C=[]
D=[]
for i in range(Q):
  a,b,c,d = map(int, input().split())
  A.append(a)
  B.append(b)
  C.append(c)
  D.append(d)  

def score(box):
  ret = 0
  for i in range(Q):
    if box[B[i]-1] - box[A[i]-1] == C[i]:
      ret += D[i]
  return(ret)

box = [1]*N
n = N - 1
flag = True
ans = 0
while flag:
#  print(box, score(box))
  ans = max(ans,score(box))
  for nn in range(1,N+1):
    n = N-nn
    if box[n] < M:
      box[n] += 1
      box[n:N] = [box[n]]*(N-n)
      break
    elif box[0]==M:
      flag = False

print(ans)

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
a=[0]*q
b=[0]*q
c=[0]*q
d=[0]*q
x=[0]*10
s=0
ans=0
for i in range(q):
  a[i],b[i],c[i],d[i]=map(int,input().split())
for a0 in range(1,m+1):
  x[0]=a0
  for a1 in range(x[0],m+1):
    x[1]=a1
    for a2 in range(x[1],m+1):
      x[2]=a2
      for a3 in range(x[2],m+1):
        x[3]=a3
        for a4 in range(x[3],m+1):
          x[4]=a4
          for a5 in range(x[4],m+1):
            x[5]=a5
            for a6 in range(x[5],m+1):
              x[6]=a6
              for a7 in range(x[6],m+1):
                x[7]=a7
                for a8 in range(x[7],m+1):
                  x[8]=a8
                  for a9 in range(x[8],m+1):
                    x[9]=a9
                    for j in range(q):
                      if x[b[j]-1]-x[a[j]-1]==c[j]:
                        s=s+d[j]
                    ans=max(ans,s)
                    s=0
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)]
# print(abcd)
ans = 0
l = range(M)
c = list(itertools.combinations_with_replacement(l,N))
# print(c)

for i in range(len(c)):
    A = c[i]
    # print(A)
    ans_i = 0
    for j in range(Q):
        A_b = A[abcd[j][1]-1]
        A_a = A[abcd[j][0]-1]
        # print("A",A_b,A_a)

        c_i = A_b-A_a
        # print(j,c_i,abcd[j])
        if c_i == abcd[j][2]:
            # print("=========")
            ans_i += abcd[j][3]
    # print(ans_i,"++++++++")
    if ans_i > ans:
        ans = ans_i

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from pprint import pprint as pp
from pprint import pformat as pf


class Data:

    def __init__(self, frm, to, diff, score):
        self.frm = frm - 1
        self.to = to - 1
        self.diff = diff
        self.score = score

    def __repr__(self):
        return "{} {} {} {}".format(
                self.frm,
                self.to,
                self.diff,
                self.score,
                )

    def calc_score(self, l):
        if l[self.to] - l[self.frm] == self.diff:
            return self.score
        else:
            return 0

def flat(l, key, value):
    for i in range(key, len(l)):
        l[i] = value

def shift(l, m, key):
    if key < 0:
        return False
    if l[key] < m:
        flat(l, key, l[key] + 1)
        return True
    else:
        return shift(l, m, key - 1)

def count(n, m):
    l = [1] * n
    key = 0
    flg = True
    while flg:
        yield l
        flg = shift(l, m, len(l) - 1)

def get_scorebook(q):
    book = [None] * q
    for i in range(q):
        a, b, c, d = list(map(int, input().split()))
        book[i] = Data(a, b, c, d)
    return book

def calc_score(l, book):
    score = 0
    for data in book:
        score += data.calc_score(l)
    return score

if __name__ == '__main__':
    n, m, q = map(int, input().split())
    scorebook = get_scorebook(q)
    score = 0
    for l in count(n, m):
        score = max(score, calc_score(l, scorebook))
    print(score)

Submission status: Accepted

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

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

ans=0

for i in range(len(aa)):
  score = 0
  for n in range(len(qset)):
    a=aa[i]
    abcd=qset[n]
    if a[abcd[1]-1]-a[abcd[0]-1]==abcd[2]:
      score=score+abcd[3]
  if ans<score:
    ans=score
print(ans)

Submission status: Accepted

Solution code:
import itertools

nmq = list(map(int, input().split()))
n = nmq[0]
m = nmq[1]
q = nmq[2]
i = [list(map(int, input().split())) for i in range(q)]
a = list(range(1, m + 1))
a_all = list(itertools.combinations_with_replacement(a, n))
ans = 0
for x in a_all:
  val = 0
  for y in i:
    if x[y[1] - 1] - x[y[0] - 1] == y[2]:
      val = val + y[3]
  if val > ans:
    ans = val
print(ans)

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)]
Max = 0
 
for a in itertools.combinations_with_replacement(range(1, M+1), N):
  A = list(a)
  A.sort()
  point = 0
  for i in range(Q):
    ai = List[i][0]
    bi = List[i][1]
    if ai < 1 or N < ai or bi < 1 or N < bi:
      continue
    if A[bi-1]-A[ai-1] == List[i][2]:
      point += List[i][3]
  if Max < point:
    Max = point
 
print(Max)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n,m,q=map(int,input().split())
x=[list(map(int,input().split())) for i in range(q)]
for i in range(q):
    for j in range(2):
        x[i][j]-=1
a=[]
def dfs(v):
    if len(v)>n:
        return
    if len(v)==n:
        a.append(v)
    for i in range(int(v[-1]),m+1):
        dfs(v+[i])
for i in range(1,m+1):
    dfs([i])
ans=0
for i in a:
    now=0
    for k in range(q):
        if i[x[k][1]]-i[x[k][0]]==x[k][2]:
            now+=x[k][3]
    ans=max(now,ans)
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

nums = []
for i in range(q):
    line = [int(s) for s in input().split()]
    line[0] -= 1
    line[1] -= 1
    nums.append(line)

candidate = []
for line in list(itertools.combinations_with_replacement(range(1, m + 1), n)):
    a = 0
    for num in nums:
        if line[num[1]] - line[num[0]] == num[2]:
            a += num[3]
    
    candidate.append(a)

print(max(candidate))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M, Q = (int(i) for i in input().split())
    T = [[int(i) for i in input().split()] for j in range(Q)]

    def dfs(A):
        cur = 0
        if len(A) == N:
            for a, b, c, d in T:
                if A[b-1] - A[a-1] == c:
                    cur += d
        elif len(A) == 0:
            for i in range(1, M+1):
                v = dfs(A + [i])
                cur = max(cur, v)
        else:
            for i in range(A[-1], M+1):
                v = dfs(A + [i])
                cur = max(cur, v)
        return cur

    print(dfs([]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
from copy import copy

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

queue = deque()
for i in range(1, M+1):
    queue.append([i])
for _ in range(N-1):
    while 1:
        if queue[0] == [1] * N:
            break
        x = queue.popleft()
        for i in range(x[-1], M+1):
            y = copy(x)
            y.append(i)
            queue.append(y)

score_max = 0
for A in queue:
    score = 0
    for a, b, c, d in X:
        if int(A[b-1]) - int(A[a-1]) == c:
            score += d
    score_max = max(score, score_max)

print(score_max)

Submission status: Accepted

Solution code:
import itertools
n,m,q = map(int,input().split())
mx = 0
a = [0]*q
b = [0]*q
c = [0]*q
d = [0]*q
for i in range(q):
  ai,bi,ci,di = map(int,input().split())
  a[i] = ai-1
  b[i] = bi-1
  c[i] = ci
  d[i] = di
mx = 0
l = [i for i in range(m)]
for v in itertools.combinations_with_replacement(l, n):
  s = 0
  for i in range(q):
    if v[b[i]] - v[a[i]] == c[i]:
      s += d[i]
  if s > mx:
    mx = s
print(mx)

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
ni = lambda:int(input())
import itertools
n,m,q = ma()
abcd = []
ls = [i+1 for i in range(m)]
for i in range(q):
    abcd.append(list(ma()))

ans = 0
for A in  itertools.combinations_with_replacement(ls,n):
    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:
from itertools import combinations_with_replacement
N, M, Q = map(int, input().split())
chk = []
for _ in range(Q):
    *abcd, = map(int, input().split())
    chk.append(abcd)

li = [list(x) for x in list(combinations_with_replacement(range(1, M+1), N))]
ans = 0
for item in li:
    sub = 0
    for c in chk:
        if item[c[1]-1] - item[c[0]-1] == c[2]:
            sub += c[3]
    ans = max(ans, sub)
print(ans)

Submission status: Accepted

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

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

ans = 0
def dfs(i,before,score):
    global ans
    if i == n - 1:
        ans = max(ans,score)
        return
    for num in range(before[i],m + 1):
        point = 0
        for a,c,d in cond[i + 1]:
            if num - before[a] == c:
                point += d
        if point > 0:
            before[i + 1] = num
            dfs(i + 1,before,score + point)
    before[i + 1] = before[i]
    dfs(i + 1,before,score) 

dfs(0,[1] + [-1]*(n - 1),0)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement


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

# ans = 0
# for i in range(1 << M):
#     num = [x + 1 for x in range(M + 1) if (i >> x) & 1]
#     K = len(num)
# if K <= N:
num = [x + 1 for x in range(M)]
ans = 0
for var in combinations_with_replacement(num, N):
    cnt = 0
    for a, b, c, d in con:
        a -= 1; b -= 1
        if var[b] - var[a] == c:
            cnt += d
    ans = max(cnt, ans)

print(ans)

Submission status: Accepted

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

A=[1]*n
#スコアけいさん
score=0
for a in Q:
    if A[a[1]-1]-A[a[0]-1]==a[2]:
        score += a[3]

max_score=score

while True:
    #つぎのAの作成
    count=0
    for i in range(1,n+1):
        if A[-i]!=m:
            next=A[-i]+1
            for j in range(1,i+1):
                A[-j]=next
            break
        else:
            count+=1

    if count==n:
        break

    #スコアけいさん
    score=0
    for a in Q:
        if A[a[1]-1]-A[a[0]-1]==a[2]:
            score += a[3]

    if score>max_score:
        max_score=score

print(max_score)

Submission status: Accepted

Solution code:
import itertools

n, m, q = map(int, input().split())
abcd = []
a_pre = [] 


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

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

sum = 0
for i in range(len(a_pre)):
  sum_pre = 0
  for j in range(len(abcd)):
    if a_pre[i][abcd[j][1] - 1] - a_pre[i][abcd[j][0] - 1] == abcd[j][2]:
      sum_pre = sum_pre + abcd[j][3]
  if sum_pre > sum:
    sum = sum_pre

print(sum)

Submission status: Accepted

Solution code:
import itertools

N, M, Q = list(map(int,input().split()))
numbers = [i for i in range(1, M+1)]
array = itertools.combinations_with_replacement(numbers, N)

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

max_score = 0
for A in array:
    score = 0
    for _ in range(Q):
        a, b, c, d = input_data[_]
        a = a - 1
        b = b - 1
        if A[b] - A[a] == c:
            score += d
    if score > max_score:
        max_score = score
    
print(max_score)

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

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

ma = 0
for elm in k:
    cnt = 0
    for j in range(q):
        if (elm[b[j]-1] - elm[a[j]-1] ==c[j]):
            cnt += d[j]
    if ma != max(ma,cnt):
        ma = cnt    
print(ma)

Submission status: Accepted

Solution code:
def cal(arr):
    tmp = 0
    for a, b, c, d in cond:
        if arr[b-1] - arr[a-1] == c:
            tmp += d
    return tmp

def dfs(arr):
    global res
    if len(arr) == N:
        res = max(res, cal(arr))
        return
    beg = 1 if len(arr) == 0 else arr[-1]
    for i in range(beg, M+1):
        dfs(arr + [i])

N, M, Q = list(map(int, input().split()))
cond = []
res = 0
for _ in range(Q):
    tmp = list(map(int, input().split()))
    cond.append(tmp)
dfs([])
print(res)

Submission status: Accepted

Solution code:
import itertools
n,m,q = map(int,input().split())
mx = 0
a = [0]*q
b = [0]*q
c = [0]*q
d = [0]*q
for i in range(q):
  ai,bi,ci,di = map(int,input().split())
  a[i] = ai-1
  b[i] = bi-1
  c[i] = ci
  d[i] = di
mx = 0
l = [i for i in range(m)]
for v in itertools.combinations_with_replacement(l, n):
  s = 0
  for i in range(q):
    if v[b[i]] - v[a[i]] == c[i]:
      s += d[i]
  if s > mx:
    mx = s
print(mx)

Submission status: Accepted

Solution code:
import itertools

n, m, q = list(map(int, input().split()))
nums = []
for i in range(q):
    nums.append(list(map(int, input().split())))
a = list(itertools.combinations_with_replacement(
    [e for e in range(1, m + 1)], n))
for i in range(len(a)):
    a[i] = sorted(a[i])
results = [0]
for j in range(len(a)):
    max_value = 0
    for i in range(q):
        if a[j][nums[i][1] - 1] - a[j][nums[i][0] - 1] == nums[i][2]:
            max_value += nums[i][3]
    else:
        results.append(max_value)

print(max(results))

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
A=[]
i=1
m+=1
while i<m:
    for a in range(i,m):
        if n==2:
            A.append([i,a])
        else:
            for b in range(a,m):
                if n==3:
                    A.append([i,a,b])
                else:
                    for c in range(b,m):
                        if n==4:
                            A.append([i,a,b,c])
                        else:
                            for d in range(c,m):
                                if n==5:
                                    A.append([i,a,b,c,d])
                                else:
                                    for e in range(d,m):
                                        if n==6:
                                            A.append([i,a,b,c,d,e])
                                        else:
                                            for f in range(e,m):
                                                if n==7:
                                                    A.append([i,a,b,c,d,e,f])
                                                else:
                                                    for g in range(f,m):
                                                        if n==8:
                                                            A.append([i,a,b,c,d,e,f,g])
                                                        else:
                                                            for h in range(g,m):
                                                                if n==9:
                                                                    A.append([i,a,b,c,d,e,f,g,h])
                                                                else:
                                                                    for j in range(h,m):
                                                                        A.append([i,a,b,c,d,e,f,g,h,j])
    i+=1
length=len(A)
if length==0:
    print(0)
else:
    l=[]
    ans=0
    for i in range(q):
        l.append(list(map(int,input().split())))
    for tmpA in A:
        tmp=0
        for tmpQ in l:
            if tmpA[tmpQ[1]-1]-tmpA[tmpQ[0]-1]==tmpQ[2]:
                tmp+=tmpQ[3]
        ans=max(tmp,ans)
    print(ans)

Submission status: Accepted

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

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

    seq = (i for i in range(m))
    comb_list = list(itertools.combinations_with_replacement(seq, n))

    max_s = 0
    for comb in comb_list:
        score = 0
        for i in range(q):
            a, b, c, d = list_[i]
            if comb[b-1] - comb[a-1] == c:
                score += d
        if score > max_s:
            max_s = score

    print(max_s)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

    max_num = 0

    l = [ i for i in range(1,m+1)]
    c_list = list(combinations_with_replacement(l, n))

    for c in reversed(c_list):
        tmp_count = 0
        for i in range(q):
            aa = num_list[i][0]
            bb = num_list[i][1]
            cc = num_list[i][2]
            dd = num_list[i][3]
            if c[bb-1] - c[aa-1] == cc:
                tmp_count += dd

        max_num = max(max_num, tmp_count)

    print(max_num)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
n,m,q=[int(i) for i in input().split()]
l=[[int(i) for i in input().split()]for i in range(q)]
a=itertools.combinations_with_replacement(range(1,m+1), n)
print(max([sum([i[3] for i in l if j[i[0]-1]+i[2]==j[i[1]-1]])for j in a]))

Submission status: Accepted

Solution code:
import itertools

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

l = [i for i in range(1, M+1)]
#print(l)
C = itertools.combinations_with_replacement(l, N)

O = []
for i in range(Q):
    a, b, c, d = [int(j) for j in input().split()]
    O.append([a, b, c, d])
    
maxl = []  
for v in C:
    #print(v)
    A = sorted(list(v))
    #print(A)    
    mans = 0 
    for a, b, c, d in O:
        #print(a, b, c, d)
        if A[b-1] - A[a-1] == c:
            mans += d
    maxl.append(mans)

print(max(maxl))

Submission status: Accepted

Solution code:
import itertools
N,M,Q=map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]
A=[]
ans=[]
for i in itertools.combinations_with_replacement(list(range(1,M+1)), N):
    A.append(i)
# print(A)
for i in A:
    ans_=0
    for j in abcd:
        if i[j[1]-1] - i[j[0]-1] == j[2]:
            ans_+=j[3]
    ans.append(ans_)
print(max(ans))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
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 li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, M, Q = mi()
abcd = li2(Q)

#N = 10

a = '0' * N
m = str(M-1)
l = [a]
#for length in range(N):
while True:
    i = N-1
    while i >= 0 and a[i] == m:
        i -= 1
    if i == -1:
        break
    a = list(a)
    num = str(int(a[i]) + 1)
    a[i] = num
    if i !=N-1:
        for j in range(i+1, N):
            a[j] = num
    tmp = ''.join(a)
    l.append(tmp)


ans = 0
for num in l:
    cnt = 0
    num = list(map(int, list(num)))
    for i in range(Q):
        if num[abcd[i][1]-1] - num[abcd[i][0]-1] == abcd[i][2]:
            cnt += abcd[i][3]

    ans = max(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m,q = map(int,input().split())
l = []
for i in range(q):
    tl = list(map(int,input().split()))
    l.append(tl)
A = range(1,m+1)
h = itertools.combinations_with_replacement(A, n)

M = 0
for v in itertools.combinations_with_replacement(A, n):
    ans = 0
    for i in l:
        a,b,c,d = i
        if v[b-1]-v[a-1] ==c :
            ans +=d 
    M = max(ans,M)
print(M)