Problem:


Problem C: Unhappy Class

Problem

  山之御船学園の1年G組は、不幸を背負った女子生徒たちが集まるクラスである。  彼女たちは、幸福になることを目標に、日々様々な試練に立ち向かう。
  

  彼女たちのクラスでは、幸福になるための試練の一環として、幸福実技科目を受講することができる。

  月曜から金曜のそれぞれ1限からN限までに授業科目の枠があり、M個の受講可能な科目がある。
  

  

  科目iは、曜日di(di = 0, 1, 2, 3, 4がそれぞれ、月曜、火曜、水曜、木曜、金曜に対応する)のai限目から始まり、連続するkiコマで行われ、それを受講したときに得られる幸福度はtiである。
  

  各生徒は、最大L個の科目を互いに重ならないように自由に選ぶことができる。どのように科目を選べば、最も高い幸福度を得られるだろうか。与えられた科目の情報から、得られる幸福度の最大値を求めてほしい。

Input

入力は以下の形式で与えられる。

N M L
d1 a1 k1 t1
d2 a2 k2 t2
...
dM aM kM tM

1行目に3つの整数N, M, Lが空白区切りで与えられる。

2行目からM+1行目に4つの整数di, ai, ki, tiが空白区切りで与えられる。

Constraints

    
2 ≤ N ≤ 8

    
0 ≤ M ≤ 300

    
0 ≤ L ≤ min(N&times;5, M)

    
0 ≤ di ≤ 4

    
1 ≤ ai ≤ N

    
1 ≤ ki

    
ai + ki - 1 ≤ N

    
1 ≤ ti ≤ 100

Output

幸福度の和の最大値を1行に出力せよ。

Sample Input 1

3 7 3
0 1 1 1
0 1 1 2
1 1 3 4
1 1 1 1
1 2 1 2
2 1 1 3
2 2 2 1

Sample Output 1

9

Sample Input 2

5 10 5
0 1 1 2
0 2 1 2
0 1 2 3
1 2 1 2
1 4 2 3
2 1 1 1
2 1 1 2
3 3 2 3
4 1 1 2
4 2 1 2

Sample Output 2

13



Sample input:
3 7 3
0 1 1 1
0 1 1 2
1 1 3 4
1 1 1 1
1 2 1 2
2 1 1 3
2 2 2 1


Sample output:
9

Submission status: Accepted

Solution code:
# AOJ 1589 Unhappy Class
# Python3 2018.7.13 bal4u

N, M, L = map(int, input().split())
tbl = [[] for i in range(45)]
for i in range(M):
	d, a, k, t = map(int, input().split())
	tbl[d*N+a-1].append((k, t))
dp = [[0 for i in range(45)] for j in range(45)]
for da in range(5*N):
	for i in range(L+1):
		if i < L:
			for k, t in tbl[da]:
				dp[da+k][i+1] = max(dp[da+k][i+1], dp[da][i]+t)				 
		dp[da+1][i] = max(dp[da+1][i], dp[da][i])
print(dp[5*N][L])

Submission status: Accepted

Solution code:
from itertools import product

n, m, l = map(int, input().split())
subjects = [[] for _ in range(5)]
for _ in range(m):
    d, a, k, t = map(int, input().split())
    subjects[d].append((a, a + k - 1, t))

for i in range(5):
    subjects[i].sort(key=lambda x:x[1])
 
#各曜日の科目数ごとの最大幸福
def calcDp(i):
    #dp[y][x] ... y科目xコマまでの最大幸福
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    sub = subjects[i]
    for init, end, value in sub:
        for y in range(n):
            new_score = dp[y][init - 1] + value
            for x in range(end, n + 1):
                dp[y + 1][x] = max(dp[y + 1][x], new_score)
    ret = []
    for i in range(n + 1):
        ret.append(max(dp[i]))
    return ret

lst = [calcDp(i) for i in range(5)]

ans = 0
for t in product(range(n + 1), repeat=5):
    if sum(t) > l:continue
    score = 0
    for i, v in enumerate(t):
        score += lst[i][v]
    ans = max(score, ans)
print(ans)