Problem: 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.

Submission attempts (in order):
def next_array(array):
	s = -1
	for x in array[::-1]:
    	if x < M:
        	break
        else:
        	s -= 1
    
    
    if s >= -N:
    	array[s] += 1
    	if s < -1:
      		for i in range(s+1,0):
      			array[i] = array[s]
        
	return array
 
def score(array, rules):
	scr = 0
	for rule in rules:
    	if (array[rule[1]-1] - array[rule[0]-1] == rule[2]):
        	scr += rule[3]
    return scr
 
 
# input
N, M, Q = map(int, input().split())
rules = []
for i in range(Q):
    a, b, c, d = map(int, input().split())
    rules.append([a, b, c, d])
    
array　= [1] * N
max_scr = 0
 
while True:
	max_scr = max(max_scr, score(array,rules)) 
	if array[0] == M:
		break 
	array = next_array(array)
    
print(max_scr)

def next_array(array):
  s = -1
  for x in array[::-1]:
    if x < M:
      break
    else:
      s -= 1
    
  
  if s >= -N:
    array[s] += 1
    if s < -1:
      for i in range(s+1,0):
        array[i] = array[s]
  
  print(array)
  return array
 
def score(array, rules):
  scr = 0
  for rule in rules:
    if (array[rule[1]-1] - array[rule[0]-1] == rule[2]):
      scr += rule[3]
      
  return scr
 
# input
N, M, Q = map(int, input().split())
rules = []

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

array = [1] * N
max_scr = 0
 
while True:
  max_scr = max(max_scr, score(array,rules)) 
  if array[0] == M:
    break 
  array = next_array(array)
    
print(max_scr)

def next_array(array):
	s = -1
	for x in array[::-1]:
    	if x < M:
        	break
        else:
        	s -= 1
    
    
    if s >= -N:
    	array[s] += 1
    	if s < -1:
      		for i in range(s+1,0):
      			array[i] = array[s]
        
	return array
 
def score(array, rules):
	scr = 0
	for rule in rules:
    	if (array[rule[1]-1] - array[rule[0]-1] == rule[2]):
        	scr += rule[3]
    return scr
 
 
# input
N, M, Q = map(int, input().split())
rules = []
for i in range(Q):
    a, b, c, d = map(int, input().split())
    rules.append([a, b, c, d])
    
array　= [1] * N
max_scr = 0
 
while True:
	max_scr = max(max_scr, score(array,rules)) 
	if array[0] == M:
		break 
	array = next_array(array)
    
print(max_scr)

def next_array(array):
  s = -1
  for x in array[::-1]:
    if x < M:
      break
    else:
      s -= 1
    
  
  if s >= -N:
    array[s] += 1
    if s < -1:
      array[s+1:] = array[s]
      
        #array[i] = array[s]
        
  return array
 
def score(array, rules):
  scr = 0
  for rule in rules:
    if (array[rule[1]-1] - array[rule[0]-1] == rule[2]):
      scr += rule[3]
      
  return scr
 
# input
N, M, Q = map(int, input().split())
rules = []
for i in range(Q):
  a, b, c, d = map(int, input().split())
  rules.append([a, b, c, d])

array = [1] * N
max_scr = 0
 
while True:
  max_scr = max(max_scr, score(array,rules)) 
  if array[0] == M:
    break 
    array = next_array(array)
    
print(max_scr)

def next_array(array):
  s = -1
  for x in array[::-1]:
    if x < M:
      break
    else:
      s -= 1
    
  
  if s >= -N:
    array[s] += 1
    if s < -1:
      for i in range(s+1,0):
        array[i] = array[s]
        
  return array
 
def score(array, rules):
  scr = 0
  for rule in rules:
    if (array[rule[1]-1] - array[rule[0]-1] == rule[2]):
      scr += rule[3]
      
  return scr
 
# input
N, M, Q = map(int, input().split())
rules = []
for i in range(Q):
  a, b, c, d = map(int, input().split())
  rules.append([a, b, c, d])

array = [1] * N
max_scr = 0
 
while True:
  max_scr = max(max_scr, score(array,rules)) 
  if array[0] == M:
    break 
    array = next_array(array)
    
print(max_scr)

def next_array(array):
  s = -1
  for x in array[::-1]:
    if x < M:
      break
    else:
      s -= 1
    
  
  if s >= -N:
    array[s] += 1
    if s < -1:
      for i in range(s+1,0):
        array[i] = array[s]
  
  print(array)
  return array
 
def score(array, rules):
  scr = 0
  for rule in rules:
    if (array[rule[1]-1] - array[rule[0]-1] == rule[2]):
      scr += rule[3]
      
  return scr
 
# input
N, M, Q = map(int, input().split())
rules = []
 
for i in range(Q):
  a, b, c, d = map(int, input().split())
  rules.append([a, b, c, d])
  
array = [1] * N
max_scr = 0
 
while True:
  max_scr = max(max_scr, score(array,rules)) 
  if array[0] == M:
    break 
  array = next_array(array)
    
print(max_scr)

def next_array(array)
	s = -1
	for x in array[::-1]:
    	if x < M:
        	break
        else:
        	s -= 1
    
    
    if s >= -N:
      array[s] += 1
      for i in range(s,0)
      	array[i] = array[s]
        
	return array

def score(array, rules)
	scr = 0
	for rule in rules:
    	if (array[rule[1]-1] - array[rule[0]-1] == rule[2]):
        	scr += rule[3]
    return scr


# input
N, M, Q = map(int, input().split())
rules = []
for i in range(Q):
    a, b, c, d = map(int, input().split())
    rules.append([a, b, c, d])
    
array　= [1] * N
max_scr = 0

while True:
  max_scr = max(max_scr, score(array,rules)) 
  if array[0] == M:
    break 
  array = next_array(array)
  
    

  

    
        	

def next_array(array):
  s = -1
  for x in array[::-1]:
    if x < M:
      break
    else:
      s -= 1
    
  
  if s >= -N:
    array[s] += 1
    if s < -1:
      for i in range(s+1,0):
        array[i] = array[s]
        
  return array
 
def score(array, rules):
  scr = 0
  for rule in rules:
    if (array[rule[1]-1] - array[rule[0]-1] == rule[2]):
      scr += rule[3]
      
  return scr

# input
N, M, Q = map(int, input().split())
rules = []
for i in range(Q):
  a, b, c, d = map(int, input().split())
  rules.append([a, b, c, d])
    
array　= [1] * N
max_scr = 0
 
while True:
  max_scr = max(max_scr, score(array,rules)) 
  if array[0] == M:
    break 
    array = next_array(array)
    
print(max_scr)

def next_array(array):
	s = -1
	for x in array[::-1]:
    	if x < M:
        	break
        else:
        	s -= 1
    
    
    if s >= -N:
      array[s] += 1
      if s < -1:
      	for i in range(s+1,0)
      		array[i] = array[s]
        
	return array
 
def score(array, rules):
	scr = 0
	for rule in rules:
    	if (array[rule[1]-1] - array[rule[0]-1] == rule[2]):
        	scr += rule[3]
    return scr
 
 
# input
N, M, Q = map(int, input().split())
rules = []
for i in range(Q):
    a, b, c, d = map(int, input().split())
    rules.append([a, b, c, d])
    
array　= [1] * N
max_scr = 0
 
while True:
  max_scr = max(max_scr, score(array,rules)) 
  if array[0] == M:
    break 
  array = next_array(array)

def next_array(array):
	s = -1
	for x in array[::-1]:
		if x < M:
			break
		else:
			s -= 1
    
    
    if s >= -N:
    	array[s] += 1
    	if s < -1:
      		for i in range(s+1,0):
      			array[i] = array[s]
        
	return array
 
def score(array, rules):
	scr = 0
    for rule in rules:
		if (array[rule[1]-1] - array[rule[0]-1] == rule[2]):
    		scr += rule[3]
    return scr
 
 
# input
N, M, Q = map(int, input().split())
rules = []
for i in range(Q):
    a, b, c, d = map(int, input().split())
    rules.append([a, b, c, d])
    
array　= [1] * N
max_scr = 0
 
while True:
	max_scr = max(max_scr, score(array,rules)) 
	if array[0] == M:
		break 
	array = next_array(array)
    
print(max_scr)

def next_array(array):
	s = -1
	for x in array[::-1]:
		if x < M:
			break
		else:
			s -= 1
    
    
    if s >= -N:
    	array[s] += 1
    	if s < -1:
      		for i in range(s+1,0):
      			array[i] = array[s]
        
	return array
 
def score(array, rules):
	scr = 0
	for rule in rules:
    	if (array[rule[1]-1] - array[rule[0]-1] == rule[2]):
        	scr += rule[3]
    return scr
 
 
# input
N, M, Q = map(int, input().split())
rules = []
for i in range(Q):
    a, b, c, d = map(int, input().split())
    rules.append([a, b, c, d])
    
array　= [1] * N
max_scr = 0
 
while True:
	max_scr = max(max_scr, score(array,rules)) 
	if array[0] == M:
		break 
	array = next_array(array)
    
print(max_scr)

def next_array(array):
  s = -1
  for x in array[::-1]:
    if x < M:
      break
    else:
      s -= 1
    
  
  if s >= -N:
    array[s] += 1
    if s < -1:
      for i in range(s+1,0):
        array[i] = array[s]

  return array
 
def score(array, rules):
  scr = 0
  for rule in rules:
    if (array[rule[1]-1] - array[rule[0]-1] == rule[2]):
      scr += rule[3]
      
  return scr
 
# input
N, M, Q = map(int, input().split())
rules = []
 
for i in range(Q):
  a, b, c, d = map(int, input().split())
  rules.append([a, b, c, d])
  
array = [1] * N
max_scr = 0
 
while True:
  max_scr = max(max_scr, score(array,rules)) 
  if array[0] == M:
    break 
  array = next_array(array)
    
print(max_scr)

Verdicts: Runtime Error

Wrong Answer

Runtime Error

Time Limit Exceeded

Time Limit Exceeded

Wrong Answer

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Accepted