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: Wrong Answer

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

abcd = list()
for _ in range(Q):
  abcd.append(list(map(int, input().split())))

di = 0
A = [1] * N
sorted_abcd = sorted(abcd, key=lambda x:x[0], reverse=True)
sorted_abcd = sorted(sorted_abcd, key=lambda x:x[3], reverse=True)
amin = 1000
amax = 0

for a, b, c, d in sorted_abcd:
  leng = N - b +1
  A[b-1:] = [A[a-1]+c-1] * leng
  if a >= amin and a <= amax:
    break
  else:
    amin = min(a, amin)
    amax = max(a, amax)
  if A != sorted(A) or A[-1] > M:
    break
  di += d
print(di)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

ans = []
import itertools
for A in itertools.combinations_with_replacement(range(1, 10), N):
    tmp = 0
    for a, b, c, d in abcd:
        if A[b-1] - A[a-1] == c:
            tmp += d
    ans.append(tmp)
print(max(ans))

Submission status: Wrong Answer

Solution code:
import sys
#input=sys.stdin.readline
sys.setrecursionlimit(3000000)

x=10
def sol(a):
    if len(a)==10:
        tmp=0
        for i in w:
            if a[i[1]-1]-a[i[0]-1]==i[2]:
                tmp+=i[3]
        ans[0]=max(ans[0],tmp)
        return
    s=a[-1] if len(a) else 1
    for i in range(s,10+1):
        a.append(i)
        sol(a)
        a.pop()

ans=[0]
n,m,q=map(int,input().split())
w=[]
for i in range(q):
    a,b,c,d=map(int,input().split())
    w.append((a,b,c,d))
#for i in w:
#    print(i)
sol([])
print(ans[0])

Submission status: Wrong Answer

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

query = []

for _ in range(Q):
    query.append(tuple(map(int, input().split())))

res = 0


def solve(A):
    global res
    if len(A) == N:
        tmp = 0
        for q in query:
            a, b, c, d = q

            if A[b - 1] - A[a - 1] == c:
                tmp += d
        res = max(res, tmp)
        return

    for i in range(A[-1], 11):
        solve(A + [i])


for i in range(1, 11):
    solve([i])
print(res)

Submission status: Wrong Answer

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

query = []

for _ in range(Q):
    query.append(tuple(map(int, input().split())))

res = 0


def solve(A):
    global res
    if len(A) == N:
        tmp = 0
        for q in query:
            a, b, c, d = q

            if A[b - 1] - A[a - 1] == c:
                tmp += d
        res = max(res, tmp)
        return

    for i in range(A[-1], 11):
        solve(A + [i])


for i in range(11):
    solve([i])
print(res)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import itertools
N,M,Q=map(int,input().split())
abcd=[]
Abase=[]
for a in range(1,M+1):
    Abase.append(a)
for _ in range(Q):
    abcd.append(list(map(int,input().split())))
A=list(itertools.combinations(Abase,N))
ans=0
for i in A:
    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: Wrong Answer

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]

# print(abcd_array)

anslist_candidates = []
create_list([], N, [1,2,3,4,5,6,7,8,9,10])
# 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('---update!---')
        #print(max_anslist_score)
        #print(anslist_candidates[max_anslist_indx])

#print('---final---')
print(max_anslist_score)
#print(anslist_candidates[max_anslist_indx])

Submission status: Wrong Answer

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+1:]
        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]

# print(abcd_array)

anslist_candidates = []
create_list([], N, [1,2,3,4,5,6,7,8,9,10])
# 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
    if sum_d > max_anslist_score:
        max_anslist_score = sum_d
        max_anslist_indx = indx

print(max_anslist_score)
#print(max_anslist_indx)

Submission status: Wrong Answer

Solution code:
import itertools

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

# 重複組み合わせ: nHr = n+r-1Cr を考える
ans = 0
R = [i for i in range(1, M+1)]
print(R)
for comb in itertools.combinations_with_replacement(R, N):
    temp = 0
    for abcd in ABCD:
        a, b, c, d = abcd
        if comb[b-1] - comb[a-1] == c:
            temp += d
    if temp >= ans:
        ans = temp

    # print("comb: {}, temp: {}, ans: {}".format(comb, temp, ans))

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
import scipy
import itertools
 
def score(arr):
    hoge = 0
    for ai,bi,ci,di in zip(a, b, c, d):
        if arr[bi-1]-arr[ai-1] == ci:
            hoge += di
    return hoge
 
def dfs(arr):
    if len(arr) == n:
        return score(arr)
    last = arr[-1] if len(arr) > 0 else 0
    res = 0
    for i in range(last, m+1):
        arr.append(i)
        res = max(res, dfs(arr))
        arr.pop()
    return res
 
def solve():
    global a, b, c, d, n, m, q
    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())
    print(dfs([]))
    return 0
 
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
import scipy
import itertools

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

def dfs(arr):
    if len(arr) == n:
        return score(arr)
    last = arr[-1] if len(arr) > 0 else 0
    res = 0
    for i in range(last, m+1):
        arr.append(i)
        res = max(res, dfs(arr))
        arr.pop()
    return res

def solve():
    global a, b, c, d, n, m, q
    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())
    print(dfs([]))
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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*3
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: Wrong Answer

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*4
generation=40
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: Wrong Answer

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

a = [0] * 55; b = [0] * 55; c = [0] * 55; d = [0] * 55

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

def socer(A):
    now = 0
    for i in range(q):
        if A[b[i]-1] - A[a[i]-1] == c[i]: now += d[i]
    return now

def dfs(A):
    print(A)
    if len(A) == n: return socer(A)
    res = 0
    last = A[-1] if A else 0
    for i in range(last, m):
        A.append(i)
        res = max(res, dfs(A))
        A.pop()
    return res
      
print(dfs([]))

Submission status: Wrong Answer

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

import itertools
ans = 0
for p in itertools.combinations_with_replacement([i for i in range(1, M+1)], N):
    tmp_ans = 0
    for i in range(Q):
        if p[b[i]] - p[a[i]] == c[i]:
            tmp_ans += d[i]
    if tmp_ans > ans:
        print(p)
        ans = tmp_ans
print(ans)

Submission status: Wrong Answer

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

ans = 0
for p in itertools.permutations([0]*(m-2)+[1]*n):
    A = [0]*n
    cnt = 1
    i = 0
    for flag in p:
        if flag == 1:
            A[i] = cnt
            i += 1
        else:
            cnt += 1
    val = 0
    for i in range(q):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            val += d[i]
    ans = max(ans,val)
print(ans)

Submission status: Wrong Answer

Solution code:
def combinations_with_replacement(elements, N):
    for element in elements:
        if N == 1:
            yield [element]
        else:
            for combination in combinations_with_replacement(elements, N-1):
                yield [element] + combination


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

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

Submission status: Wrong Answer

Solution code:
n,m,q=map(int,input().split())
abcd=[]
x=[1]
for i in range(q):
    abcd.append(list(map(int,input().split())))
ans=0
def dfs(s):
    global ans
    if(len(s)==n):
        t=0
        for a,b,c,d in abcd:
            if(s[b-1]-s[a-1]==c):
                t+=d
        ans=max(t,ans)
        return 
    p=s[-1]
    print(s)
    while p<=m:
        s.append(p)
        dfs(s)
        p=s.pop()+1
dfs(x)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

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

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')

from itertools import combinations_with_replacement as comb

def solve():
    n, m, q = MI()
    A = [0] * q
    B = [0] * q
    C = [0] * q
    D = [0] * q

    for i in range(q):
        a, b, c, d = MI()
        A[i] = a - 1
        B[i] = b - 1
        C[i] = c
        D[i] = d

    # print(A, B)
    ans = 0
    for idx, j in enumerate(comb([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], r=n)):
        # print(j)
        point = 0
        for k in range(q):
            # print(B[k], A[k])
            if j[B[k]] - j[A[k]] == C[k]:
                point += D[k]
        ans = max(ans, point)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
def make(n, A, M):
    if n == 0:
        A_list.append(A)
        return
    for i in range(A[-1], M+1):
        make(n-1, A+[i], M)

n, M, q = map(int, input().split())
A_list = []
for i in range(M+1):
    make(n, [i], M)
# print(A_list)

abcd = [list(map(int, input().split())) for _ in range(q)]
ans = 0
for i in A_list:
    tmp = 0
    for a,b,c,d in abcd:
        if i[b] - i[a] == c:
            tmp += d
    ans = max(ans, tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
from collections import deque
N,M,Q=map(int,input().split())
a=deque([])
b=a
c=a
d=a
o=0
for i in range(Q):
    u,v,x,y=map(int,input().split())
    a.append(u)
    b.append(v)
    c.append(x)
    d.append(y)
l=list(itertools.combinations(range(M+N), N))
for x in l:
    e=a
    f=b
    g=c
    h=d
    s=0
    u=[]
    for i in range(N):
        u.append(x[i]-i)
    for i in range(Q):
        if u[f[0]-1]-u[e[0]-1]-g[0]==0:
            s+=h[0]
            e.popleft()
            f.popleft()
            g.popleft()
            h.popleft()
    if s>o:
        o=s
print(o)

Submission status: Wrong Answer

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

ans =0

from itertools import combinations_with_replacement

for i in combinations_with_replacement(range(1,m+1), n):
    print(i)
    tmp=0
    for j in range(q):
        if c[j] == i[b[j]-1] - i[a[j]-1]:
            tmp += d[j]
    ans = max( ans, tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N,M,Q=map(int,input().split())
a=[]
b=[]
c=[]
d=[]
o=0
for i in range(Q):
    u,v,x,y=map(int,input().split())
    a.append(u)
    b.append(v)
    c.append(x)
    d.append(y)
l=list(itertools.combinations(range(M+N), N))
for x in l:
    s=0
    u=[]
    for i in range(N):
        u.append(x[i]-i)
    for i in range(Q):
        if u[b[i]-1]-u[a[i]-1]-c[i]==0:
            s+=d[i]
    if s>o:
        o=s
print(o)

Submission status: Wrong Answer

Solution code:
N,M,Q = map(int,input().split())
li = []
counter = 0
n = []
for s in range(Q):
    li.append(list(map(int,input().split())))

for i in range(10**(N-1),10**N):
    k = str(i)
    for q in range(Q):
        if int(k[li[q][1]-1]) -  int(k[li[q][0]-1]) ==  int(li[q][2]):
            counter +=  int(li[q][3])
    n.append(counter)
    counter = 0
print(max(n))

Submission status: Wrong Answer

Solution code:
import itertools as it

n,m,q = map(int,input().split())
seq = [i+1 for i in range(m)]*m
two = [[0]*4 for i in range(q)]
ans = 0
seq.sort()
com = list(it.combinations(seq,n))

for i in range(q):
    two[i][0],two[i][1],two[i][2],two[i][3] = map(int,input().split())

for i in range(len(com)):
    score = 0
    for j in range(q):
        if com[i][two[j][1]-1]-com[i][two[j][0]-1] == two[j][2]:
            score += two[j][3]
    if ans < score:
        ans = score

print(ans)

Submission status: Wrong Answer

Solution code:
a, b, n = list(map(lambda x: int(x), input().split(' ')))

print((a * (n - 1)) // b - a * ((n - 1) // b))

Submission status: Wrong Answer

Solution code:
from collections import deque

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])
            print(cur + [next])
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: Wrong Answer

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

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

ans = 0 

def dfs(A):
    if len(A) == n+1:
        now = 0 
        global ans 
        for i in range(q):
            if A[b[i]] - A[a[i]] == c[i]:
                now += d[i]
        ans = max([ans, now])
        return

    A.append(A[-1])
    while A[-1] <= m:
        dfs(A)
        A[-1] += 1

# main
A = [1] 
dfs(A)
print(ans)

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]
ans = 0
anslst = [0] * N

def dfs(cnt):
    global ans
    if cnt == N:
        total = 0
        for i in range(Q):
            if anslst[abcd[i][1] - 1] - anslst[abcd[i][0] - 1] == abcd[i][2]:
                total += abcd[i][3]
        ans = max(ans, total)
        return

    for i in range(M):
        anslst[cnt] = i + 1
        dfs(cnt + 1)
    return

dfs(0)

print(ans)

Submission status: Wrong Answer

Solution code:
n,M,q=map(int,input().split())
a=[]
for i in range(q):
    a.append(list(map(int,input().split())))
A=[1]
res=0
m=[]
for i in range(1,n):
    m.clear()
    for j in range(M-A[i-1]+2):
        ma=0
        for ad in a:
            if ad[1]-1==i:
                if A[i-1]+j-A[ad[0]-1]==ad[2]:
                    ma+=ad[3]
        m.append(ma)
    A.append(A[i-1]+m.index(max(m)))
    res+=max(m)
print(res)

Submission status: Wrong Answer

Solution code:
from itertools import combinations_with_replacement
n, m, q = map(int, input().split())
A = combinations_with_replacement(range(1, m), n)
L = []

for _ in range(q):
    L.append(list(map(int, input().split())))

r = 0
for a in A:
    t = 0
    for l in L:
        if a[l[1] - 1] - a[l[0] - 1] == l[2]:
            t += l[3]
    if t > r:
        r = t
print(r)

Submission status: Wrong Answer

Solution code:
from itertools import combinations_with_replacement

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


def calc(l):
    score = 0
    for a, b, c, d in cond:
        if l[b] - l[a] == c:
            score += d
    return score


ans = 0
l = [0] * n
l[0] = 1


def dfs(l_len):
    global l, ans
    if l_len == n:
        ans = max(ans, calc(l))
        return

    for i in range(l[l_len - 1], m + 1):
        l[l_len] = i
        dfs(l_len + 1)


dfs(0)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M,Q = map(int,input().split())
lis = []
i = 0
ai,bi,dist,poin = [],[],[],[]
while True:
    try:
        lis.append(list(map(int,input().split())))
        ai.append(lis[i][0])
        bi.append(lis[i][1])
        dist.append(lis[i][2])
        poin.append(lis[i][3])
        i+=1

    except:
        break;
        #または、quit(),os.exit()をして止める。

def point(num):
  tok = 0
  for i in range(Q):
    if(num[ai[i]-1] - num[bi[i]-1] == dist[i]):
      tok += poin[i]
  return tok

#per = [M**i for i in range(1,N+1)].sort()

def UpdateA(num):
  NewA = num
  flag = 0
  i = N-1
  while(flag == 0 and i >= 0):
    NewA[i] += 1
    if(NewA[i] > M):
      NewA[i] = 1
      i -= 1
    else:
      flag = 1
  return NewA
  
maxi = 0
A = [1 for i in range(N)]
while(1):
  if(Q == 1):
    maxi = poin[0]
    break
  thisp = point(A)
  if(thisp > maxi):
    maxi = thisp
  A = UpdateA(A)
  if(sum(A) == N):
    break

print(maxi)

Submission status: Wrong Answer

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

l = []

def inc(ary):
  ary[-1] += 1
  for i in range(len(ary)-1, -1, -1):
    v = ary[i]
    if v > m:
      if i == 0:
        return False
      ary[i-1] += 1
      ary[i] = ary[i-1]
  return ary

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

a_tmp = [1] * n
# print(n, m, q)
# print(l)
# print(a_tmp)

ans = 0
l_len = len(l)
while True:
  ans_tmp = 0
  for i in range(l_len):
    a, b, c, d = l[i]
    if (a_tmp[b] - a_tmp[a]) == c:
      ans_tmp += d
  if ans_tmp > ans:
    ans = ans_tmp
  
  # a_tmp のインクリメント
  a_tmp = inc(a_tmp)
  if a_tmp == False:
    break
    
print(ans)

Submission status: Wrong Answer

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

l = []

def inc(ary):
  ary[-1] += 1
  for i in range(len(ary)-1, -1, -1):
    v = ary[i]
    if v > m:
      if i == 0:
        return False
      ary[i] = ary[i-1]
      ary[i-1] += 1
  return ary

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

a_tmp = [1] * n
# print(n, m, q)
# print(l)
# print(a_tmp)

ans = 0
l_len = len(l)
while True:
  ans_tmp = 0
  for i in range(l_len):
    a, b, c, d = l[i]
    if (a_tmp[b] - a_tmp[a]) == c:
      ans_tmp += d
  if ans_tmp > ans:
    ans = ans_tmp
  
  # a_tmp のインクリメント
  a_tmp = inc(a_tmp)
  if a_tmp == False:
    break
    
print(ans)

Submission status: Wrong Answer

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

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)

a_list = []
  
for i in range(10):
  a_list.append(i)

suuretsu_list = itertools.combinations_with_replacement(a_list, n)

point_list = [0]

for suuretsu in suuretsu_list:
  point = 0
  for _a, _b, _c, _d in zip(a, b, c, d):
    if suuretsu[_b - 1] - suuretsu[_a - 1] == _c:
      point += _d
  point_list.append(point)
print(max(point_list))

Submission status: Wrong Answer

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

l = []

def inc(ary):
  ary[-1] += 1
  for i in range(len(ary)-1, -1, -1):
    v = ary[i]
    if v > m:
      if i == 0:
        return False
      ary[i-1] += 1
      ary[i] = 1
  return ary

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

a_tmp = [1] * n
# print(n, m, q)
# print(l)
# print(a_tmp)

ans = 0
l_len = len(l)
while True:
  ans_tmp = 0
  for i in range(l_len):
    a, b, c, d = l[i]
    if (a_tmp[b] - a_tmp[a]) == c:
      ans_tmp += d
  if ans_tmp > ans:
    ans = ans_tmp
  
  # a_tmp のインクリメント
  a_tmp = inc(a_tmp)
  if a_tmp == False:
    break
    
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
def main():
    N, M, Q = map(int, input().split())
    abcd = []
    for _ in range(Q):
        a, b, c, d = map(int, input().split())
        abcd.append((a-1, b-1, c, d))
    #abcd = sorted(abcd, reverse=True, key=lambda x: x[3])
    A = [1] * N
    #print(abcd)
    for a, b, c, d in abcd:
        #print(a , b , c , d)
        if A[b] - A[a] != c and A[a] + c <= M:
            score_before = get_score(A, abcd)
            A_ = copy.deepcopy(A)
            A_[b] = A_[a] + c
            for i in range(b, N-1):
                if A_[i+1] < A[i]:
                    if A[i+1] + 1 <= M:
                        A[i+1] += 1
                    else:
                        A[i+1] = M
            score_after = get_score(A_, abcd)
            if score_after > score_before:
                A = A_
    #print(A)
    print(get_score(A, abcd))
            

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

l = []

def inc(ary):
  s = ''
  ary[-1] += 1
  for i in range(len(ary)-1, -1, -1):
    v = ary[i]
    if v > m:
      if i == 0:
        return False
      ary[i-1] += 1
      ary[i] = i+1
  return ary

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

a_tmp = [1] * n
# print(n, m, q)
# print(l)
# print(a_tmp)

ans = 0
l_len = len(l)
while True:
  ans_tmp = 0
  for i in range(l_len):
    a, b, c, d = l[i]
    if (a_tmp[b] - a_tmp[a]) == c:
      ans_tmp += d
  if ans_tmp > ans:
    ans = ans_tmp
  
  # a_tmp のインクリメント
  a_tmp = inc(a_tmp)
  if a_tmp == False:
    break
    
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
def main():
    N, M, Q = map(int, input().split())
    abcd = []
    for _ in range(Q):
        a, b, c, d = map(int, input().split())
        abcd.append((a-1, b-1, c, d))
    abcd = sorted(abcd, reverse=True, key=lambda x: x[3])
    A = [1] * N
    #print(abcd)
    for a, b, c, d in abcd:
        #print(a , b , c , d)
        if A[b] - A[a] != c and A[a] + c <= M:
            score_before = get_score(A, abcd)
            A_ = copy.deepcopy(A)
            A_[b] = A_[a] + c
            for i in range(b, N-1):
                if A_[i+1] < A[i]:
                    if A[i+1] + 1 <= M:
                        A[i+1] += 1
                    else:
                        A[i+1] = M
            score_after = get_score(A_, abcd)
            if score_after > score_before:
                A = A_
    #print(A)
    print(get_score(A, abcd))
            

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m,q = map(int,input().split())
abcd = [list(map(int,input().split())) for _ in range(q)]
ans = 0
for a in range(1,11):
  for b in range(a,11):
    for c in range(b,11):
      for d in range(c,11):
        for e in range(d,11):
          for f in range(e,11):
            for g in range(f,11):
              for h in range(g,11):
                for i in range(h,11):
                  for j in range(i,11):
                    lst = [0,a,b,c,d,e,f,g,h,i,j]
                    s = 0
                    for l in range(q):
                      s += abcd[l][3]*(lst[abcd[l][1]]-lst[abcd[l][0]]==abcd[l][2])
                    ans = max(ans, s)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

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

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

ans = 0
for A in A_list:
    sum = 0
    for a,b,c,d in abcd:
        if A[b-1] - A[a-1] == c:
            sum += d
    ans = max(ans, sum)

print(ans)

Submission status: Wrong Answer

Solution code:
def dfs(A, M, i):
  if i < 0:
    return
  A[i] += 1
  if A[i] > M:
    dfs(A, M, i-1)
    if i-1 >= 0:
      A[i] = A[i-1]

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)

A = [1]*N
ans = 0

for _ in range(10000):
  dsum = 0
  for i in range(Q):
    ai,bi,ci,di = a[i], b[i], c[i], d[i]
    if A[bi-1]-A[ai-1] == ci:
      dsum += di
  ans = max(ans, dsum)

  #終了条件
  if A[0]==M:
    break

  #終了しない場合は次の数字
  dfs(A, M, N-1)

print(ans)