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 = map(int,input().split())
xy = []
for _ in range(q):
  a,b,c,d = map(int,input().split())
  a = n-a
  b = n-b
  xy.append([a,b,c,d])
time = [0 for _ in range(n)]
def nex(time):
  cnt = 0
  for d in range(n):
    if time[d] == m-1:
      cnt += 1
    else:
      break
  if cnt == n:
    return 'over'
  else:
    se = time[cnt] + 1
  for d in range(cnt):
    time[d] = se
  time[cnt] += 1
  return time
can = []
while time != 'over':
  tmp = 0
  #print(time)
  for x in xy:
    a,b,c,d = x
    #print(time,a,b,time[a]-time[b])
    if time[b] - time[a] == c:
      tmp += d
  can.append(tmp)  
  time = nex(time)
print(max(can))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)
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,B,C,D=map(int,input().split())
    a[i]=A;b[i]=B;c[i]=C;d[i]=D
r=[]
def dfs(i,depth,b,h):
    if depth==0:
        b.append(h)
        return
    for j in range(i,M+1):
        nh=h[:]
        nh.append(j)
        dfs(j,depth-1,b,nh)
dfs(1,10,r,[])
ans=0
for R in r:
    cnt=0
    for j in range(Q):
        if R[b[j]-1]-R[a[j]-1]==c[j]:
            cnt+=d[j]
    ans=max(cnt,ans)
print(ans)

Submission status: Accepted

Solution code:
#MLE注意！0や1のケースに注意

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

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

    def dfs(l):
        res = 0
        if len(l)==n:
            for a,b,c,d in abcd:
                if l[b-1]-l[a-1]==c:
                    res += d
            return res
        else:
            a = l[-1]
            for i in range(a, m+1):
                temp = l + [i]
                res = max(res, dfs(temp))
            return res
    print(dfs([1]))

if __name__ == '__main__':
    main()

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 = list(itertools.combinations_with_replacement(list(range(1, m+1)), n))

max_score = 0

for a in A:
  score = 0
  for abcd in ABCD:
    if a[abcd[1]-1]-a[abcd[0]-1]==abcd[2]:
      score += abcd[3]
  max_score = max(max_score, score)
  
print(max_score)

Submission status: Accepted

Solution code:
import itertools


N, M, Q = map(int, input().split())
query = [tuple(map(int, input().split())) for _ in range(Q)]
ans = 0
for p in itertools.combinations_with_replacement(range(1, M+1), N):
    A = list(p)
    s = 0
    for a, b, c, d in query:
        s += d if A[b-1]-A[a-1] == c else 0
    ans = max(ans, s)
print(ans)

Submission status: Accepted

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

L = set()
def h(l):
    if len(l) == N:
        L.add(l)
        return
    s = 0
    if len(l) == 0:
        s = 1
    else:
        s = l[-1]
    for i in range(s, M+1):
        h(l + (i,))


h(())

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

ans = 0


for l in L:
    t = 0
    for a,b,c,d in z:
        if l[b] - l[a] == c:
            t += d
    ans = max(ans, t)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor

def possible_list(n, m):
    mlist = list(range(1, m+1))
    for comb in combinations_with_replacement(mlist, n):
        comb = sorted(comb)
        yield comb

def main():
    N, M, Q = map(int, input().split())
    constraints = []
    for i in range(Q):
        a, b, c, d = map(int, input().split())
        constraints.append((a, b, c, d))

    maxvalue = 0
    for l in possible_list(N, M):
        total = 0
        for a, b, c, d in constraints:
            if l[b-1] - l[a-1] == c:
                total += d
        if total > maxvalue:
            maxvalue = total

    print(maxvalue)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

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

ml = [i for i in range(1, m+1)]
ans = 0
for i in itertools.combinations_with_replacement(ml, n):
    point = 0
    for a, b, c, d in abcd:
        if i[b-1] - i[a-1] == c:
            point += d
    ans = max(ans, point)

print(ans)

Submission status: Accepted

Solution code:

import math
import itertools
import sys
import collections

def solve(N,M,Q,ABCD):
    ans = 0
    A = [i for i in range(1,M+1)]
    for p in itertools.combinations_with_replacement(A,N):
        tmp = 0
        for a,b,c,d in ABCD:
            if(p[b-1] - p [a-1] == c):
                tmp+=d
        ans = max(ans,tmp)
    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:
#!/usr/bin/env python3
n, m, q = map(int, input().split())
from itertools import*
t = 0
l = [list(map(int, input().split())) for _ in range(q)]
for i in combinations_with_replacement(range(1, m+1), n):
    s = 0
    for a, b, c, d, in l:
        if i[b-1] - i[a-1] == c: s += d
    t = max(t, s)
print(t)

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
a=[]
b=[]
c=[]
d=[]
for i in range(q):
	ai,bi,ci,di=map(int,input().split())
	a.append(ai)
	b.append(bi)
	c.append(ci)
	d.append(di)
from itertools import combinations_with_replacement as cmb
A=list(cmb(range(1,m+1),n))
#print(A)
ans=0
for lst in A:
	sum=0
	for i in range(q):
		if lst[b[i]-1]-lst[a[i]-1]==c[i]:
			sum+=d[i]
	ans=max(sum,ans)
print(ans)

Submission status: Accepted

Solution code:
from collections import *
ans = 0
def calc(l):
	global ans
	res = 0
	for i in q:
		if l[i[1]-1]-l[i[0]-1] == i[2]:
			res += i[3]
	ans = max(ans,res)
def rec(ind,p,l):
	if(ind == n):
		calc(l)
		return
	for i in range(p,m+1):
		l.append(i)
		rec(ind+1,i,l)
		l.pop()
n,m,Q = map(int,input().split())
q = []
for i in range(Q):
	q.append(list(map(int,input().split())))
rec(0,1,[])
print(ans)

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
ABCD = [tuple(map(int, input().split())) for _ in range(Q)]


max_score = 0


def search(A):
    global max_score

    if len(A) == N:
        score = 0
        for a, b, c, d in ABCD:
            if A[b - 1] - A[a - 1] == c:
                score += d
        max_score = max(score, max_score)
        return

    for a_next in range(A[-1], M + 1):
        search(A + [a_next])


for i in range(1, M + 1):
    search([i])


print(max_score)

Submission status: Accepted

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


def readstr():
    return input().strip()


def readint():
    return int(input())


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


def readstrs():
    return input().split()


N, M, Q = readnums()
num_list = [list(readnums()) for _ in range(Q)]

ans = 0
for v in combinations_with_replacement(range(1, M + 1), N):
    val = 0
    for n in num_list:
        if v[n[1] - 1] - v[n[0] - 1] == n[2]:
            val += n[3]
    ans = max(ans, val)

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement


def main():
    n,m,q = map(int,input().split())
    num_lst = []
    for i in range(q):
        num_lst.append(list(map(int,input().split())))
    l = list(range(1,m+1))
    A = list(combinations_with_replacement(l,n))

    mx = 0
    for now_A in A:
        score = 0
        for nums in num_lst:
            a,b,c,d = nums
            if now_A[b-1] - now_A[a-1] == c:
                score += d
        mx = max(mx,score)
    print(mx)



if __name__ == '__main__':
    main()

Submission status: Accepted

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

def score(List):
    res = 0
    for a, b, c, d in ques:
        if List[b] - List[a] == c:
            res += d

    return res


def dfs(i, x):
    res = 0
    if i == n:
        return score(x)

    for j in range(max(x[-1], 1), m+1):
        res = max(res, dfs(i+1, x+[j]))

    return res

print(dfs(0, [0]))

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)]
nums = []
maxp = 0

for i in range(M):
    nums.append(i+1)

for retsu in itertools.combinations_with_replacement(nums, N):
    p = 0
    for i in range(Q):
        a = abcd[i][0]-1
        b = abcd[i][1]-1
        c = abcd[i][2]
        d = abcd[i][3]
        if retsu[b]-retsu[a] == c:
            p += d
    maxp = max(p,maxp)
    
print(maxp)

Submission status: Accepted

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

num = 0
nax = 0

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

for com in list(itertools.combinations_with_replacement(nums, n)):
    num = 0
    for j in range(q):
        if com[l[j][1]-1]-com[l[j][0]-1] == l[j][2]:
            num += l[j][3]
    nax = max(num, nax)
print(nax)

Submission status: Accepted

Solution code:
import sys
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()))

import itertools

n,m,q=MAP()

a=[list(MAP()) for i in range(q)]

ans=0
for ls in list(itertools.combinations_with_replacement(range(1,m+1), n)):
    res=0
    for i in range(len(a)):
        if ls[a[i][1]-1]-ls[a[i][0]-1]==a[i][2]:
            res+=a[i][3]
    if ans<=res:
        ans=res
print(ans)

Submission status: Accepted

Solution code:
import itertools


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

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

for seq in seqs:
    point = 0
    for query in queries:
        a, b, c, d = query
        if seq[b-1] - seq[a-1] == c:
            point += d
    if point > ans:
        ans = point

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m,q = inpl()
abc = [inpl() for _ in range(q)]
q = deque()
q.append([1])
res = 0

while q:
    now = q.popleft()
    if len(now) == n:
        ans = 0
        for i,x in enumerate(abc):
            a,b,c,d = x
            b -= 1; a -= 1
            if now[b] - now[a] == c:
                ans += d
        res = max(ans, res)
        continue
    for i in range(now[-1], m+1):
        q.append(now + [i])
print(res)

Submission status: Accepted

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

def dfs(vec, mx, cnt):
    if cnt:
        tmp = 0
        for i in range(mx, m+1):
           tmp = max(tmp, dfs(vec+[i], i, cnt-1))
        return tmp
    else:
        tmp = 0
        for i in range(q):
            if vec[b[i]]-vec[a[i]]==c[i]: tmp += d[i]
        return tmp
print(dfs([], 1, n))

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    from sys import stdin
    # from collections import defaultdict
    # import math
    input = stdin.readline

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

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

    # print(abcd)
    ans = 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):
                                            num = [a, b, c, d, e, f, g, h, i, j]
                                            num_sum = 0
                                            for k, l, o, p in abcd:
                                                if num[l]-num[k] == o:
                                                    num_sum += p
                                            # print(num_sum)
                                            if num_sum > ans:
                                                ans = num_sum
    print(ans)

Submission status: Accepted

Solution code:
N,M,Q = [int(v) for v in input().split()]

querys = [[int(v) for v in input().split()] for _ in range(Q)]

ans = 0
L = []

def dfs(now,last = 1):
    if len(now) == N:
        L.append(now)
        return

    for i in range(1,M+1):
        if i >= last:
            c = now[:]
            c.append(i)
            dfs(c,last=i)

dfs([1])

for l in L:
    tmp = 0
    for q in querys:
        a,b,c,d = q
        if l[b-1] - l[a-1] == c: tmp+= d
    ans = max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
from math import gcd
from itertools import combinations_with_replacement

def readlines(n):
    for _ in range(n):
        a, b, c, d = map(int, input().split())
        yield a-1, b-1, c, d

def main():
    n, m, q = map(int, input().split())
    X = list(readlines(q))

    for comb in combinations_with_replacement(range(1, m+1), n):
        x = 0
        for a, b, c, d in X:
            if comb[b] - comb[a] == c:
                x += d
        yield x

print(max(main()))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, Q: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):

    def cal_p (l):
        p = 0
        for ai,bi,ci,di in zip(a,b,c,d):
            if l[bi-1]-l[ai-1] == ci:
                p+=di
        return p

    max_p = [0]

    def ser (l, prev, dep):
        if dep == N:
            # print(l)
            return cal_p(l)
        else:
            for i in range(prev, M+1):
                max_p[0] = max(ser(l + [i], i, dep+1), max_p[0])
            return 0
    
    max_p = max(ser([],1,0), max_p[0])
    print(max_p)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    a = [int()] * (Q)  # type: "List[int]"
    b = [int()] * (Q)  # type: "List[int]"
    c = [int()] * (Q)  # type: "List[int]"
    d = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
        d[i] = int(next(tokens))
    solve(N, M, Q, a, b, c, d)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
n,m,q = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(q)]
l = []
for i in range(1,m+1):
    l.append(i)
#print(l)
l_list = list(itertools.combinations_with_replacement(l,n))
#print(l_list)

ans = 0
#print(len(l_list))
for i in range(len(l_list)):
    b = 0
    for j in range(q):
        if (l_list[i][a[j][1]-1] - l_list[i][a[j][0]-1] == a[j][2]):
            b += a[j][3]
    #print(b)
    if (ans < b):
        ans = b
print(ans)

Submission status: Accepted

Solution code:
import itertools
import sys
N, M, Q = map(int, input().split())
abcd = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

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

best_score = 0
for A in A_cand:
    d_sum = 0
    for i in range(Q):
        a = abcd[i][0] - 1
        b = abcd[i][1] - 1
        c = abcd[i][2]
        d = abcd[i][3]
        if A[b] - A[a] == c:
            d_sum += d
    if best_score < d_sum:
        best_score = d_sum

print(best_score)

Submission status: Accepted

Solution code:
def dfs(x, y):
    if len(x) == n:
        l.append(x)
        return
    else:
        for i in range(y, m+1):
            z = list(x)
            z.append(i)
            dfs(z, i)
        return

n, m, q = map(int, input().split())
ans = 0
l = []
dfs([], 1)
A = []
B = []
C = []
D = []
for _ in range(q):
    a, b, c, d = map(int, input().split())
    A.append(a-1)
    B.append(b-1)
    C.append(c)
    D.append(d)
for i in range(len(l)):
    cnt = 0
    for j in range(q):
        if l[i][B[j]]-l[i][A[j]] == C[j]:
            cnt += D[j]
    ans = max(cnt, ans)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools
N,M,Q = map(int,input().split())
X = []
for _ in range(Q):
    a,b,c,d = map(int,input().split())
    X.append([a,b,c,d])
Y = [i for i in range(1,M+1)]
Z = list(itertools.combinations_with_replacement(Y,N))
#print(Z)
ans = 0
for z in Z:
    #print(z)
    tmp = 0
    for x in X:
        #print(x)
        if z[x[1]-1] - z[x[0]-1] == x[2]:
            tmp += x[3]
    #print(tmp)
    if tmp > ans:
        ans = tmp
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import combinations_with_replacement

def input():
    return stdin.readline().strip()


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

    ans = 0
    for seq in combinations_with_replacement(range(1, M + 1), N):
        score = 0
        for i in range(Q):
            if seq[b[i]] - seq[a[i]] == c[i]:
                score += d[i]

        ans = max(ans, score)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools


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

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

ans = 0
for A in itertools.combinations_with_replacement(all, N):
    point = 0
    for i in range(Q):
        ai, bi, ci, di = abcd[i]
        if A[bi - 1] - A[ai - 1] == ci:
            point += di
    ans = max(point, ans)

print(ans)

Submission status: Accepted

Solution code:
import itertools as it
import numpy as np

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

arange =  np.arange(1,M+1)
As = list(it.combinations_with_replacement(arange,N))

m = 0
for A in As:
    tmp = 0
    for q in a:
        if A[q[1]-1] - A[q[0]-1] == q[2]:
            tmp += q[3]
    if m < tmp:
        m = tmp

print(m)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)
from itertools import combinations, combinations_with_replacement


#def solve(N: int, M: int, Q: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
def solve(n, m, Q, a, b, c, d, X):
    cans = list(combinations_with_replacement(range(1, m + 1), n))
    #print(cans)
    ret = 0
    for can in cans:
        tmp = 0
        for i in range(Q):
            if can[b[i] - 1] - can[a[i] - 1] == c[i]:
                tmp += d[i]
        ret = max(tmp, ret)
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    a = [int()] * (Q)  # type: "List[int]"
    b = [int()] * (Q)  # type: "List[int]"
    c = [int()] * (Q)  # type: "List[int]"
    d = [int()] * (Q)  # type: "List[int]"
    X = []
    for i in range(Q):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
        d[i] = int(next(tokens))
        X.append((a[i], b[i], c[i], d[i]))
    solve(N, M, Q, a, b, c, d, X)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

import sys
# sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
# arr = [[int(el) for el in input().split()] for i in range(n)]

import itertools

def cal(n, m, q, arr):

    def cal_set(s):

        score = 0
        s_arr = list(s)
        l = len(s_arr)

        for a, b, c, d, in arr:
            if 0 <= a - 1 < l and 0 <= b - 1 < l:
                if s_arr[b - 1] - s_arr[a - 1] == c:
                    score += d

        return score

    max_score = 0

    comb_list = itertools.combinations_with_replacement(list(range(m)), n)

    for s in comb_list:
        max_score = max(max_score, cal_set(s))

    return max_score


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

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

print (cal(n, m, q, arr))

Submission status: Accepted

Solution code:


def main():
    N, M, Q = [int(x) for x in input().split()]
    queries = [[int(x) for x in input().split()] for _ in range(Q)]

    ans = float("-inf")
    import itertools
    for A in itertools.combinations_with_replacement(range(1, M+1), N):
        # print(A)
        s = 0
        for a, b, c, d in queries:
            if A[b-1] - A[a-1] == c:
                s += d
        ans = max(ans, s)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:


import itertools as itt
def resolve():
    N,M,Q = map(int,input().split())
    
    abcd = [list(map(int,input().split())) for i in range(Q)]
    mx = 0
    for A in itt.combinations_with_replacement(range(1,M+1),N):
        score =0

        for a,b,c,d in abcd:
            if A[b-1]-A[a-1]==c:
                score+=d
        mx = max(score,mx)
    print(mx)





if __name__ == "__main__":
    #unittest.main()
    resolve()

Submission status: Accepted

Solution code:
from collections import deque

#　listからr個を順に取り出す順列、戻り値はイテレーター
# itertools.permutations(list, n)
# listからr個を選ぶ組み合わせ、戻り値はイテレーター
# itertools.permutations(list, n)

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

ans = 0
tmp = []

def dfs():
    global tmp
    stack = deque([[[], 0]])
    while stack:
        cur, i = stack.pop()
        if i == n:
            tmp.append(cur)
            continue
        mi = 1
        if i:
            mi = cur[-1]
        for next in range(mi, m+1):
            stack.append([cur+[next], i+1])
dfs()
# print(tmp)

for item in tmp:
    cand = 0
    for a, b, c, d in abcd:
        if item[b-1] - item[a-1] == c:
            cand += d
    ans = max(ans, cand)

print(ans)

Submission status: Accepted

Solution code:
N,M,Q = map(int,input().split())
L = list(range(1,M+1))
X = list()
for i in range(Q):
  X.append(list(map(int,input().split())))
  
ans = 0

import itertools
for l in itertools.combinations_with_replacement(L, N):
  l = sorted(list(l))
  s = 0
  for a,b,c,d in X:
    if l[b-1]-l[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())
query = []
for i in range(Q):
    query.append(list(map(int, input().split())))

As = list(itertools.combinations_with_replacement(range(1, M+1), N))
ans = 0
for a in As:
    point = 0
    for q in query:
        if a[q[1]-1] - a[q[0]-1] == q[2]:
            #print(a, " + ", q)
            point += q[3]
    ans = max(ans, point)
    #print(point)

#print(As)
#print(query)
print(ans)

Submission status: Accepted

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

import itertools

def main():
     n, m, q = map(int, input().split())
     q_list = list()
     a_list = [i for i in range(1, m+1)]

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

     ans = 0

     for v in itertools.combinations_with_replacement(a_list, n):
          target = list(v)
          # print('target: {}'.format(target))
          score = 0
          for i in range(len(q_list)):
               point = q_list[i]
               # print('point: {}'.format(point))
               if target[point[1]-1] - target[point[0]-1] == point[2]:
                    score += point[3]
          
          if ans < score:
               ans = score
          
     print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
ptn = []
for i in range(Q):
    a,b,c,d = map(int, input().split())
    ptn.append([a-1,b-1,c,d])
mx = 0
def calc(arr):
    if len(arr) == N:
        global mx
        tot = 0
        #print(arr)
        #print(ptn)
        for i in range(Q):
            if arr[ptn[i][1]] - arr[ptn[i][0]] == ptn[i][2]:
                tot += ptn[i][3]
        mx = max(mx, tot)
        return
    for i in range(1,M+1):
        if i < arr[-1]: continue
        calc(arr+[i])
for i in range(1,M+1):
    calc([i])
print(mx)

Submission status: Accepted

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

queue = [((1,), 1)]
maxvalue = 0
while queue:
    xs, n = queue.pop()
    if n == N:
        t = 0
        for a, b, c, d in abcd:
            if xs[b] - xs[a] == c:
                t += d
        maxvalue = max(t, maxvalue)
        continue
    for i in range(xs[n - 1], M + 1):
        queue.append((xs + (i,), n + 1))
print(maxvalue)

Submission status: Accepted

Solution code:
import sys
import itertools
import numpy as np

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

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

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

n = len(A)
score = np.zeros(n, np.int32)
m = map(int, read().split())
for a, b, c, d in zip(m, m, m, m):
    cond = A[:, b - 1] - A[:, a - 1] == c
    score += d * cond

print(score.max())

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,M,Q = map(int, readline().split())
    abcd = []
    for _ in range(Q):
        a,b,c,d = map(int, readline().split())
        abcd.append((a,b,c,d))

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

    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

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

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

def check(n, m, l, a):
    if len(a) == n:
        point = 0
        for i in range(len(l)):
            if a[l[i][1]-1]-a[l[i][0]-1] == l[i][2]:
                point += l[i][3]
        return point
    point = 0
    if len(a) == 0:
        start = 1
    else:
        start = a[-1]
    for i in range(start, m+1):
        point = max(point, check(n, m, l, a+[i]))
    return point

print(check(n, m, l, []))

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 = list(range(1,m+1))

ptr = list(itertools.combinations_with_replacement(A, n))

ans = 0

for i in ptr:
    tmp = 0
    for a,b,c,d in abcd:
        if i[b-1] - i[a-1] == c:
            tmp += d
    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

def point(A):
    res = 0
    for i in range(Q):
        if x[i][1] > len(A):
            continue
        else:
            if A[x[i][1]-1] - A[x[i][0]-1] == x[i][2]:
                res += x[i][3]
    return res


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

ans = 0
for A in combinations_with_replacement(range(1, M+1), N):
    ans = max(ans, point(A))

print(ans)