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: Time Limit Exceeded

Solution code:
nmq=list(map(int, input().split()))
N=nmq[0]
M=nmq[1]
Q=nmq[2]
ablist=[list(map(int, input().split())) for i in range(Q)]
sumlist=[]
alist=[i for i in range(1,M+1)]
import itertools as ite
case=list(ite.combinations_with_replacement(alist,N))
for nowcase in case:
    sumd=0
    for i in range(Q):
        a=ablist[i][0]
        b=ablist[i][1]
        c=ablist[i][2]
        d=ablist[i][3]
        aa=nowcase[a-1]
        ab=nowcase[b-1]
        if ab-aa==c:
            sumd+=d
    sumlist.append(sumd)
print(max(sumlist))

Submission status: Time Limit Exceeded

Solution code:
nmq=list(map(int, input().split()))
N=nmq[0]
M=nmq[1]
Q=nmq[2]
ablist=[list(map(int, input().split())) for i in range(Q)]
sumlist=[]
alist=[i for i in range(1,M+1)]
import itertools as ite
case=list(ite.combinations_with_replacement(alist,N))
for nowcase in case:
    sumd=0
    for i in range(Q):
        a=ablist[i][0]
        b=ablist[i][1]
        c=ablist[i][2]
        d=ablist[i][3]
        aa=nowcase[a-1]
        ab=nowcase[b-1]
        if ab-aa==c:
            sumd+=d
    sumlist.append(sumd)
sumlist.sort(reverse=True)
print(sumlist[0])

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = list(map(int, input().strip().split()))
pattern_list = []
for _ in range(Q):
	pattern = tuple(map(int, input().strip().split()))
	pattern_list.append(pattern)

def create(N,M):
	S = [[] for _ in range(N+1)]
	for m in range(1,M+1):
		S[1].append([m])
	for n in range(1,N):
		for s in S[n]:
			Max = s[-1]
			for i in range(Max, M+1):
				S[n+1].append(s+[i])
	return S

highest = 0
for letters in create(N,M)[N]:
	point = 0
	for a,b,c,d in pattern_list:
		if int(c) == letters[int(b-1)]-letters[int(a-1)]:
			point += d
	highest = max([highest, point])

print(highest)

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = list(map(int, input().strip().split()))
pattern_list = []
shortest = 0
for _ in range(Q):
	pattern = tuple(map(int, input().strip().split()))
	shortest = max([shortest, pattern[0], pattern[1]])
	pattern_list.append(pattern)

def create(N,M):
	S = [[] for _ in range(N+1)]
	for m in range(1,M+1):
		S[1].append([m])
	for n in range(1,N):
		for s in S[n]:
			Max = s[-1]
			for i in range(Max, M+1):
				S[n+1].append(s+[i])
	return S

highest = 0
for n, n_letters in enumerate(create(N, M)):
	if n < shortest: continue
	for letters in n_letters:
		point = 0
		for a,b,c,d in pattern_list:
			if int(c) == letters[int(b-1)]-letters[int(a-1)]:
				point += d
		highest = max([highest, point])

print(highest)

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = list(map(int, input().strip().split()))
pattern_list = []
shortest = []
for _ in range(Q):
	pattern = tuple(map(int, input().strip().split()))
	shortest += [pattern[0], pattern[1]]
	pattern_list.append(pattern)
shortest = max(shortest)

def create(N,M):
	S = [[] for _ in range(N+1)]
	for m in range(1,M+1):
		S[1].append([m])
	for n in range(1,N):
		for s in S[n]:
			Max = s[-1]
			for i in range(Max, M+1):
				S[n+1].append(s+[i])
	return S

highest = 0
for n, n_letters in enumerate(create(N, M)):
	if n < shortest: continue
	for letters in n_letters:
		point = 0
		for a,b,c,d in pattern_list:
			if int(c) == letters[int(b-1)]-letters[int(a-1)]:
				point += d
		highest = max([highest, point])

print(highest)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import product


def feasible(abcd, N, M):
    # assume abcd sorted
    A = [0] * (N+1)
    a, b, c, d = abcd.pop(0)
    A[a] = 1
    A[b] = c + 1
    while len(abcd) > 0:
        a, b, c, d = abcd.pop(0)
        if A[a] == 0 and A[b] == 0:
            abcd.append([a, b, c, d])
        elif A[a] != 0 and A[b] != 0:
            if A[b] - A[a] != c:
                return False
        elif A[b] == 0:
            A[b] = A[a] + c
            if A[b] > M:
                return False
            if max(A[:b]) > A[b]:
                return False
            if min([x for x in A[b:] if x > 0]) < A[b]:
                return False
        else:  # A[a] == 0
            A[a] = A[b] - c
            if A[a] < 1:
                return False
            if max(A[:a]) > A[a]:
                return False
            if min([x for x in A[a:] if x > 0]) < A[a]:
                return False
    return True


def main():
    N, M, Q = [int(x) for x in input().split()]
    abcd = [[int(x) for x in input().split()] for _ in range(Q)]
    if Q == 1:
        return abcd[0][3]
    abcd.sort()
    sf = [[sum([x[3] if y else 0 for x,y in zip(abcd, f)]), f]
          for f in product([1,0], repeat=Q) if f.count(True)>=2]
    sf.sort(reverse=True)
    for s, f in sf:
        target = [x for x,y in zip(abcd, f) if y]
        if feasible(target, N, M):
            return s
    return max([x[3] for x in abcd])


print(main())

Submission status: Time Limit Exceeded

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


abcdList = []
for _ in range(q):
  abcd = list(map(int, input().split()))
  abcdList.append(abcd)
aList = []
def createA(tempA, x, t):
  if x!=0:
      tempA.append(t)
  if x == n:
    abc = []
    for item in tempA:
        abc.append(item)
    aList.append(abc)
    return
  x += 1
  for i in range(t, m+1):
    if x == 1:
        tempA = []
    createA(tempA, x, i)
    tempA.pop(-1)



x = 0
createA([], x, 1)
maxAns = 0
for item in aList:
  ans = 0
  for i in range(q):
    b = abcdList[i][1]
    a = abcdList[i][0]
    c = abcdList[i][2]
    d = abcdList[i][3]
    if item[b-1] - item[a-1] == c:
      ans += d
  if ans > maxAns:
    maxAns = ans
print(maxAns)

Submission status: Time Limit Exceeded

Solution code:
import copy
n,m,q=map(int,input().split())
List=[]
for i in range(q):
  a,b,c,d=map(int,input().split())
  List.append([a,b,c,d])
List.sort()
s=-1
for i in range(2 ** q):
    l=[-1]*9
    l.insert(0,1)
    l.insert(0,1)
    point=0
    for j in range(q):
      if ((i >> j) & 1):
        point+=List[j][3]
        if l[List[j][0]]!=-1 and l[List[j][1]]!=-1 and l[List[j][1]]-l[List[j][0]]!=List[j][2]:
          l[0]=-2
          break
        else:
          if l[List[j][0]]==-1 and l[List[j][1]]!=-1:
            l[List[j][0]]=l[List[j][1]]-List[j][2]
          elif l[List[j][0]]!=-1 and l[List[j][1]]==-1:
            l[List[j][1]]=l[List[j][0]]+List[j][2]
          elif l[List[j][0]]==-1 and l[List[j][1]]==-1:
            if l[List[j][1]]!=l[List[j][1]]+List[j][2]:
              l[0]=-2
              break
    x=copy.deepcopy(l)
    while -1 in x:x.remove(-1)
    if 1<=min(x) and max(x)<=m:
          y=copy.deepcopy(x)
          x.sort()
          if x==y and point>s:
            s=point
print(s)

Submission status: Time Limit Exceeded

Solution code:
#C
import itertools
import numpy as np
n, m, q = list(map(int, input().split()))
a = np.zeros(q)
b = np.zeros(q)
c = np.zeros(q)
d = np.zeros(q)
ans = 0
for i in range(q):
    a[i], b[i], c[i], d[i] = list(map(int, input().split()))
for A in itertools.combinations_with_replacement(range(1,m+1),n):
    new_ans = 0
    for i in range(q):
        if A[int(b[i])-1] - A[int(a[i])-1] == c[i]:
            new_ans += d[i]
    ans = max(ans, new_ans)
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import itertools
N,M,Q=map(int,input().split())
abcd=[]
for _ in range(Q):
    abcd.append(tuple(map(int,input().split())))
Abase=[]
for a in range(1,M+1):
    Abase=Abase+[a]*N
A=set(itertools.combinations(Abase,N))
A2=set([tuple(sorted(x)) for x in A])
ans=0
for i in A2:
    temp=0
    for j in abcd:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            temp=temp+j[3]
    if temp>=ans:
        ans=temp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import itertools
N,M,Q=map(int,input().split())
abcd=[]
for _ in range(Q):
    abcd.append(list(map(int,input().split())))
Abase=[]
for a in range(1,M+1):
    Abase.append(a)
Abase2=[]
for _ in range(N):
    Abase2=Abase2+Abase
A=set(itertools.combinations(Abase2,N))
A2=set([tuple(sorted(x)) for x in A])
ans=0
for i in A2:
    temp=0
    for j in abcd:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            temp=temp+j[3]
    if temp>=ans:
        ans=temp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import itertools
N,M,Q=map(int,input().split())
abcd=[]
for _ in range(Q):
    abcd.append(list(map(int,input().split())))
Abase=[]
for a in range(1,M+1):
    Abase.append(a)
Abase2=[]
for _ in range(N):
    Abase2=Abase2+Abase
A=set(itertools.combinations(Abase2,N))
A=list(A)
A2=set([tuple(sorted(x)) for x in A])
ans=0
for i in A2:
    temp=0
    for j in abcd:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            temp=temp+j[3]
    if temp>=ans:
        ans=temp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import itertools
N,M,Q=map(int,input().split())
abcd=[]
for _ in range(Q):
    abcd.append(list(map(int,input().split())))
Abase=[]
for a in range(1,M+1):
    Abase.append(a)
Abase2=[]
for _ in range(N):
    Abase2=Abase2+Abase
A=set(itertools.combinations(Abase2,N))
A=list(A)
A2=[sorted(x) for x in A]
ans=0
for i in A2:
    temp=0
    for j in abcd:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            temp=temp+j[3]
    if temp>=ans:
        ans=temp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import itertools
N,M,Q=map(int,input().split())
abcd=[]
for _ in range(Q):
    abcd.append(list(map(int,input().split())))
Abase=[]
for a in range(1,M+1):
    Abase.append(a)
Abase=Abase*N
A=set(itertools.combinations(Abase,N))
A=list(A)
A2=[sorted(x) for x in A]
ans=0
for i in A2:
    temp=0
    for j in abcd:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            temp=temp+j[3]
    if temp>=ans:
        ans=temp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations_with_replacement
 
n, m, q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(q)]
 
l = list(range(1,m+1))
big_a = combinations_with_replacement(l, n)
list_a = list(big_a)
#print(list_a)
s = []
   
  
for j in range(len(list_a)):
    nowa = list_a[j]
    z = 0
    #print(abcd[z
    o =[]
    while z <= q-1:
        p = abcd[z]
        aa = int(p[0])
        bb = int(p[1])
        cc = int(p[2])
        dd = int(p[3])
        #a = int(aa)
        #b = int(bb)
        #c = int(cc)
        #d = int(dd)
       
        s_b = int(nowa[bb-1])
        s_a = int(nowa[aa-1])
        if s_b - s_a == cc:
            o.append(dd)
            #print(o)
        else:
            pass
        s.append(sum(o))
        z += 1
 
 
#print(s)
print(max(s))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import itertools
N,M,Q=map(int,input().split())
abcd=[]
for _ in range(Q):
    abcd.append(list(map(int,input().split())))
Abase=[]
for a in range(1,M+1):
    Abase.append(a)
Abase=Abase*N
A=list(itertools.combinations(Abase,N))
A2=[sorted(x) for x in A]
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]
A2=get_unique_list(A2)
ans=0
for i in A2:
    temp=0
    for j in abcd:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            temp=temp+j[3]
    if temp>=ans:
        ans=temp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import itertools
N,M,Q=map(int,input().split())
abcd=[]
for _ in range(Q):
    abcd.append(list(map(int,input().split())))
Abase=[]
for a in range(1,M+1):
    Abase.append(a)
Abase=Abase*N
A=list(itertools.combinations(Abase,N))
A2=[sorted(x) for x in A]
ans=0
for i in A2:
    temp=0
    for j in abcd:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            temp=temp+j[3]
    if temp>=ans:
        ans=temp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import queue

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)

q = queue.Queue()
order = 1
point = 0
ans = 0

for i in range(1,m+1):
    q.put([i])

while order < n:
    ion = q.get()
    order = len(ion)
    top = ion[0]
    if order == n:
        q.put(ion)
        break
    for i in range(1,top + 1):
        nice = [i]
        nice = nice + ion
        q.put(nice)

while not q.empty():
    point = 0
    tre = q.get()
    for i in range(Q):
        a = A[i] - 1
        b = B[i] - 1
        c = C[i]
        d = D[i]
        a1 = tre[a]
        a2 = tre[b]
        a3 = a2 - a1
        if a3 == c:
            point += d
    ans = max(point,ans)

print('{}'.format(ans))

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import queue
import math

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)

q = queue.Queue()
ion = 1
order = 1
point = 0
ans = 0

for i in range(1,m+1):
    q.put([i])

while order < n:
    ion = q.get()
    order = len(ion)
    top = ion[0]
    if order == n:
        q.put(ion)
        break
    for i in range(1,top + 1):
        nice = [i]
        nice = nice + ion
        q.put(nice)

while not q.empty():
    point = 0
    tre = q.get()
    for i in range(Q):
        a = A[i] - 1
        b = B[i] - 1
        c = C[i]
        d = D[i]
        a1 = tre[a]
        a2 = tre[b]
        a3 = a2 - a1
        if a3 == c:
            point += d
    ans = max(point,ans)

print('{}'.format(ans))

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import queue
import math

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

A,B,C,D = [],[],[],[]
seq = ""

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)

q = queue.Queue()
ion = 1
order = 1
point = 0
ans = 0

for i in range(1,m+1):
    q.put([i])

while order < n:
    ion = q.get()
    order = len(ion)
    top = ion[0]
    if order == n:
        q.put(ion)
        break
    for i in range(1,top + 1):
        nice = ion.copy()
        nice.reverse()
        nice.append(i)
        nice.reverse()
        q.put(nice)

while not q.empty():
    point = 0
    tre = q.get()
    for i in range(Q):
        a = A[i] - 1
        b = B[i] - 1
        c = C[i]
        d = D[i]
        a1 = int(tre[a])
        a2 = int(tre[b])
        a3 = a2 - a1
        if a3 == c:
            point += d
    ans = max(point,ans)

print('{}'.format(ans))

Submission status: Time Limit Exceeded

Solution code:
def permutations(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutations(data):
                ret.append([i] + j)

        return ret
        

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

bou = [1] * N
ball = [2] * (M-1)

junretsu = permutations(bou + ball)

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)

#print(junretsu)
ans = 0
for i in range(len(junretsu)):
    souwa = 0
    check = 0
    A = []
    for j in range(N+M-1):
        if junretsu[i][j] == 1:
            A.append(j - check + 1)
            check += 1
    #print(A)
    for j in range(Q):
        if (A[b[j]-1] - A[a[j]-1]) == c[j]:
            souwa += d[j]
    
    ans = max(ans, souwa)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, m, q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(q)]
 
l = list(range(1,m+1))
big_a = itertools.combinations_with_replacement(l, n)
list_a = list(big_a)
#print(list_a)
s = []
   
  
for j in range(len(list_a)):
    nowa = list_a[j]
    z = 0
    #print(abcd[z
    o =[]
    while z <= q-1:
        p = abcd[z]
        aa = int(p[0])
        bb = int(p[1])
        cc = int(p[2])
        dd = int(p[3])
        #a = int(aa)
        #b = int(bb)
        #c = int(cc)
        #d = int(dd)
       
        s_b = int(nowa[bb-1])
        s_a = int(nowa[aa-1])
        if s_b - s_a == cc:
            o.append(dd)
            #print(o)
        else:
            pass
        s.append(sum(o))
        z += 1
 
 
#print(s)
print(max(s))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# Atcoder necoak answer
# https://atcoder.jp/contests/abc165/tasks/abc165_c

import numpy as np
from itertools import combinations_with_replacement

# def create_list(tmp_anslist, zan_length, zan_num_list):
#     if zan_length == 0:
#         anslist_candidates.append(tmp_anslist)
#         return
#     
#     for i, num in enumerate(zan_num_list):
#         more_zan_num_list = zan_num_list[i:]
#         create_list(tmp_anslist + [num], zan_length-1, more_zan_num_list)

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

abcd_array = np.empty((Q, 4), dtype=int)

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

# anslist_candidates = []
# create_list([], N, [ax for ax in range(1, M+1)])
# print(anslist_candidates)

anslist_candidates = combinations_with_replacement(range(1, M+1), N)


max_anslist_score = 0
for tmp_anslist in anslist_candidates:
    sum_d = 0

    is_valid_anslist = True
    prev_ansitem = tmp_anslist[0]
    for ansitem in tmp_anslist[1:]:
        if prev_ansitem > ansitem:
            is_valid_anslist = False
            break
    if not is_valid_anslist:
        continue

    for ai, bi, ci, di in abcd_array:
        #print('ai:%d, bi:%d, ci:%d, di:%d' % (ai, bi, ci, di))
        #print('tmp_anslist:%s' % (tmp_anslist))
        if ((tmp_anslist[bi-1] - tmp_anslist[ai-1]) == ci):
            sum_d += di
    #print('%s : %d' % (tmp_anslist, sum_d))
    max_anslist_score = max(max_anslist_score, sum_d)

print(max_anslist_score)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# Atcoder necoak answer
# https://atcoder.jp/contests/abc165/tasks/abc165_c

import numpy as np
from itertools import combinations_with_replacement

# def create_list(tmp_anslist, zan_length, zan_num_list):
#     if zan_length == 0:
#         anslist_candidates.append(tmp_anslist)
#         return
#     
#     for i, num in enumerate(zan_num_list):
#         more_zan_num_list = zan_num_list[i:]
#         create_list(tmp_anslist + [num], zan_length-1, more_zan_num_list)


in_nmq=input()
in_n, in_m, in_q = in_nmq.split()
N = int(in_n)
M = int(in_m)
Q = int(in_q)

abcd_array = np.empty((Q, 4), dtype=int)

for i in range(Q):
    in_abcd = input()
    in_a, in_b, in_c, in_d = in_abcd.split()
    a = int(in_a)
    b = int(in_b)
    c = int(in_c)
    d = int(in_d)
    abcd_array[i] = [a, b, c, d]

# anslist_candidates = []
# create_list([], N, [ax for ax in range(1, M+1)])
# print(anslist_candidates)

anslist_candidates = combinations_with_replacement(range(1, M+1), N)


max_anslist_score = 0
for tmp_anslist in anslist_candidates:
    sum_d = 0

    is_valid_anslist = True
    prev_ansitem = tmp_anslist[0]
    for ansitem in tmp_anslist[1:]:
        if prev_ansitem > ansitem:
            is_valid_anslist = False
            break
    if not is_valid_anslist:
        continue

    for ai, bi, ci, di in abcd_array:
        #print('ai:%d, bi:%d, ci:%d, di:%d' % (ai, bi, ci, di))
        #print('tmp_anslist:%s' % (tmp_anslist))
        if ((tmp_anslist[bi-1] - tmp_anslist[ai-1]) == ci):
            sum_d += di
    #print('%s : %d' % (tmp_anslist, sum_d))
    max_anslist_score = max(max_anslist_score, sum_d)

print(max_anslist_score)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# Atcoder necoak answer
# https://atcoder.jp/contests/abc165/tasks/abc165_c

import numpy as np
from itertools import combinations_with_replacement

# def create_list(tmp_anslist, zan_length, zan_num_list):
#     if zan_length == 0:
#         anslist_candidates.append(tmp_anslist)
#         return
#     
#     for i, num in enumerate(zan_num_list):
#         more_zan_num_list = zan_num_list[i:]
#         create_list(tmp_anslist + [num], zan_length-1, more_zan_num_list)


in_nmq=input()
in_n, in_m, in_q = in_nmq.split()
N = int(in_n)
M = int(in_m)
Q = int(in_q)

abcd_array = np.empty((Q, 4), dtype=int)

for i in range(Q):
    in_abcd = input()
    in_a, in_b, in_c, in_d = in_abcd.split()
    a = int(in_a)
    b = int(in_b)
    c = int(in_c)
    d = int(in_d)
    abcd_array[i] = [a, b, c, d]

# anslist_candidates = []
# create_list([], N, [ax for ax in range(1, M+1)])
# print(anslist_candidates)

anslist_candidates = combinations_with_replacement(range(1, M+1), N)


max_anslist_score = 0
for tmp_anslist in anslist_candidates:
    sum_d = 0

    is_valid_anslist = True
    prev_ansitem = tmp_anslist[0]
    for ansitem in tmp_anslist[1:]:
        if prev_ansitem > ansitem:
            is_valid_anslist = False
    if not is_valid_anslist:
        continue

    for ai, bi, ci, di in abcd_array:
        #print('ai:%d, bi:%d, ci:%d, di:%d' % (ai, bi, ci, di))
        #print('tmp_anslist:%s' % (tmp_anslist))
        if ((tmp_anslist[bi-1] - tmp_anslist[ai-1]) == ci):
            sum_d += di
    #print('%s : %d' % (tmp_anslist, sum_d))
    max_anslist_score = max(max_anslist_score, sum_d)

print(max_anslist_score)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# Atcoder necoak answer
# https://atcoder.jp/contests/abc165/tasks/abc165_c

import numpy as np
from itertools import combinations_with_replacement

# def create_list(tmp_anslist, zan_length, zan_num_list):
#     if zan_length == 0:
#         anslist_candidates.append(tmp_anslist)
#         return
#     
#     for i, num in enumerate(zan_num_list):
#         more_zan_num_list = zan_num_list[i:]
#         create_list(tmp_anslist + [num], zan_length-1, more_zan_num_list)


in_nmq=input()
in_n, in_m, in_q = in_nmq.split()
N = int(in_n)
M = int(in_m)
Q = int(in_q)

abcd_array = np.empty((Q, 4), dtype=int)

for i in range(Q):
    in_abcd = input()
    in_a, in_b, in_c, in_d = in_abcd.split()
    a = int(in_a)
    b = int(in_b)
    c = int(in_c)
    d = int(in_d)
    abcd_array[i] = [a, b, c, d]

# anslist_candidates = []
# create_list([], N, [ax for ax in range(1, M+1)])
# print(anslist_candidates)

anslist_candidates = combinations_with_replacement(range(1, M+1), N)


max_anslist_score = 0
for indx, tmp_anslist in enumerate(anslist_candidates):
    sum_d = 0

    is_valid_anslist = True
    prev_ansitem = tmp_anslist[0]
    for ansitem in tmp_anslist[1:]:
        if prev_ansitem > ansitem:
            is_valid_anslist = False
    if not is_valid_anslist:
        continue

    for ai, bi, ci, di in abcd_array:
        #print('ai:%d, bi:%d, ci:%d, di:%d' % (ai, bi, ci, di))
        #print('tmp_anslist:%s' % (tmp_anslist))
        if ((tmp_anslist[bi-1] - tmp_anslist[ai-1]) == ci):
            sum_d += di
    #print('%s : %d' % (tmp_anslist, sum_d))
    max_anslist_score = max(max_anslist_score, sum_d)

print(max_anslist_score)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# Atcoder necoak answer
# https://atcoder.jp/contests/abc165/tasks/abc165_c

import numpy as np

def create_list(tmp_anslist, zan_length, zan_num_list):
    if zan_length == 0:
        anslist_candidates.append(tmp_anslist)
        return 
    
    for i, num in enumerate(zan_num_list):
        more_zan_num_list = zan_num_list[i:]
        create_list(tmp_anslist + [num], zan_length-1, more_zan_num_list)

in_nmq=input()
in_n, in_m, in_q = in_nmq.split()
N = int(in_n)
M = int(in_m)
Q = int(in_q)

abcd_array = np.empty((Q, 4), dtype=int)

for i in range(Q):
    in_abcd = input()
    in_a, in_b, in_c, in_d = in_abcd.split()
    a = int(in_a)
    b = int(in_b)
    c = int(in_c)
    d = int(in_d)
    abcd_array[i] = [a, b, c, d]

anslist_candidates = []
create_list([], N, [ax for ax in range(1, M+1)])
# print(anslist_candidates)

max_anslist_indx = 0
max_anslist_score = 0
for indx, tmp_anslist in enumerate(anslist_candidates):
    sum_d = 0
    for ai, bi, ci, di in abcd_array:
        #print('ai:%d, bi:%d, ci:%d, di:%d' % (ai, bi, ci, di))
        #print('tmp_anslist:%s' % (tmp_anslist))
        if ((tmp_anslist[bi-1] - tmp_anslist[ai-1]) == ci):
            sum_d += di
    #print('%s : %d' % (tmp_anslist, sum_d))
    if sum_d > max_anslist_score:
        max_anslist_score = sum_d
        max_anslist_indx = indx

print(max_anslist_score)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

number = []
for i in range(m):
    number.append(i+1)
a = list(itertools.combinations_with_replacement(number,n))
length = len(a)
memo = [0] * length

for i in range(q):
    num = list(map(int,input().split()))
    for j in range(length):
        if int(a[j][num[1]-1])-int(a[j][num[0]-1]) == int(num[2]):
            memo[j] += num[3]
print(max(memo))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import math

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

number = []
for i in range(m):
    number.append(i+1)
a = list(itertools.combinations_with_replacement(number,n))
length = len(a)
memo = [0] * length

for i in range(q):
    num = list(map(int,input().split()))
    for j in range(length):
        if int(a[j][num[1]-1])-int(a[j][num[0]-1]) == int(num[2]):
            memo[j] += num[3]
print(max(memo))

Submission status: Time Limit Exceeded

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

n, m, q = map(int, input().split())
abcd = [input() for _ in range(q)]
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, abcd[i].split())

comb = [1] * n + [0] * (m - 1)
combination_all = set(itertools.permutations(comb))  # 5!通り出力する
all_array = []
#print(combination_all)
for i in combination_all:
    tmp = 1
    lis = []
    for j in range(len(i)):
        if i[j]:
            lis.append(tmp)
        else:
            tmp += 1
    all_array.append(lis)
#print(all_array)
ans = 0  # maxをとる
for arr in all_array:
    val = 0
    for j in range(q):
        if arr[b[j] - 1] - arr[a[j] - 1] == c[j]:
            val += d[j]
    ans = max(ans, val)
print(ans)
# bit 全探索で i が成り立つと仮定する
# 連結する奴の中で最大と最小の差がN-1以下なら成立
"""ans = 0

for i in range(2**n):
    score = 0
    emerge = []
    lis = []
    for j in range(n):
        if i>>j & j:
            if a[i] in emerge:"""

Submission status: Time Limit Exceeded

Solution code:
import itertools
import math

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

memo = []
number = []
for i in range(m):
    number.append(i+1)
len = m

for j in range(math.factorial(n+m-1)//(math.factorial(n)*math.factorial(m-1))):
    memo.append(0)

a = list(itertools.combinations_with_replacement(number,n))
for i in range(q):
    num = list(map(int,input().split()))
    for j in range(math.factorial(n+m-1)//(math.factorial(n)*math.factorial(m-1))):
        if int(a[j][num[1]-1])-int(a[j][num[0]-1]) == int(num[2]):
            memo[j] += num[3]
print(max(memo))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import itertools
N, M, Q = map(int,input().split())
L = list(itertools.combinations_with_replacement(range(1, M + 1), N))
D = []
for i in range(Q):
    D.append(list(map(int,input().split())))

#print(L)
#全てのA

ans = 0
for A in L:
    tmp = 0
    for i in range(Q):
        a = D[i][0]
        b = D[i][1]
        c = D[i][2]
        d = D[i][3]
        if A[b-1] - A[a-1] == c:
            tmp += d
        
        ans = max(ans,tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import random
from copy import deepcopy

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

gene_length=n
individual_length=n*10
generation=100
elite_gene=1
individual_mutation=0.01
gene_mutation=0.01

def get_population():
  pop=[]
  for i in range(individual_length):
    pop.append([random.randrange(1,m+1) for j in range(gene_length)])
  return pop


def get_fitness(indiv):
  fitness=0
  for a,b,c,d in l:
    a-=1
    b-=1
    if indiv[b]-indiv[a]==c:
      fitness+=d
  return fitness


def elite_selection(pop):
  pop.sort(reverse=True, key=lambda x:x[1])
  return pop[:elite_gene+1]


def two_point_crossover(parent1,parent2):
  r1=random.randint(0,gene_length-1)
  r2=random.randint(0,gene_length-1)
  child=deepcopy(parent1)
  child[r1:r2]=parent2[r1:r2]
  return child


pop=[[p,get_fitness(p)] for p in get_population()]
pop.sort(reverse=True,key=lambda x:x[1])

for g in range(generation):
  elites=elite_selection(pop)
  pop=elites
  while len(pop)<individual_length:
    if random.random()<individual_mutation:
      child=[random.randrange(1,m+1) for j in range(gene_length)]
    else:
      m1=random.randint(0,len(elites)-1)
      m2=random.randint(0,len(elites)-1)
      child=two_point_crossover(elites[m1][0],elites[m2][0])
    pop.append([child,get_fitness(child)])

    n_pop=[]
    for i in pop:
      if i not in n_pop:
        n_pop.append(i)
    pop=n_pop

  pop.sort(reverse=True,key=lambda x:x[1])

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

Submission status: Time Limit Exceeded

Solution code:
def cwrlp(data,r):
	if r <= 0:
		return []
	
	result = []
	_cwrlp(data, r, 0, [], result)
	return result

def _cwrlp(data, r, start, progress, result):
	if r == 0:
		result.append(progress)
		return
	
	for i in range(start, len(data)):
		_cwrlp(data, r-1, i, progress + [data[i]], result)

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

dataset = cwrlp(range(1,m+1),n)

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