Go: ///
// File:  2502.go
// Author: ymiyamoto
//
// Created on Sat Mar 24 00:44:45 2018
//
package main

import (
	"fmt"
)

type phrase struct {
	s, l, p int
}

const melody_len int = 393

var n, m int

func max(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func main() {
	fmt.Scan(&n)

	phrases := make([]phrase, n)
	max_count := 0
	for i := 0; i < n; i++ {
		fmt.Scan(&phrases[i].s, &phrases[i].l, &phrases[i].p)
		max_count += phrases[i].l
	}

	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, melody_len+1)
	}

	for i := range phrases {
		s := phrases[i].s
		l := phrases[i].l
		p := phrases[i].p
		for j := range dp[i] {
			for k := s; k <= l; k++ {
				if 0 <= j-k {
					dp[i+1][j] = max(dp[i+1][j], max(dp[i][j], dp[i+1][j-k]+p))
				} else {
					dp[i+1][j] = max(dp[i+1][j], dp[i][j])
				}
			}
		}
	}

	fmt.Scan(&m)
	var invalid bool
	var points []int
	for i := 0; i < m; i++ {
		var m int
		fmt.Scan(&m)
		if dp[n][m] == 0 {
			invalid = true
		}
		points = append(points, dp[n][m])
	}

	if invalid {
		fmt.Println(-1)
	} else {
		for _, p := range points {
			fmt.Println(p)
		}
	}
}

Python: from operator import itemgetter

m_inf = float("-inf")
n = int(input())
phrase = [0]*(394)
for s, l, p in (map(int, input().split()) for _ in [0]*n):
    for i, _p in enumerate(phrase[s:l+1], start=s):
        phrase[i] = _p if _p > p else p

dp = [0] + [m_inf]*393
for length, p in filter(itemgetter(1), enumerate(phrase)):
    for from_p, to_p, to in zip(dp, dp[length:], range(length, 395)):
        dp[to] = to_p if to_p >= from_p+p else from_p+p

result = [dp[int(input())] for _ in [0]*int(input())]
print(*(result if m_inf not in result else [-1]), sep="\n")

Python: import sys
sys.setrecursionlimit(100000)

n = int(input())
lyric = [tuple(map(int, input().split(" "))) for i in range(n)]
m = int(input())
melody = [int(input()) for i in range(m)]
max_melody = max(melody)
lis = [[0]+[None]*(max_melody) for j in range(n)]

def maxpoint(remin, j = n-1, _cache=lis):
    if _cache[j][remin] is not None:
        return _cache[j][remin]
    else:
        if j > 0:
            ans = maxpoint(remin, j-1)
        else:
            ans = -1
        if lyric[j][0] <= remin:
            for reduc in range(lyric[j][0], min(lyric[j][1], remin) + 1):
                cand = maxpoint(remin - reduc, j)
                if cand != -1:
                    ans = max(ans, cand + lyric[j][2])
        _cache[j][remin] = ans
        return ans

def points():
    l = []
    for i in range(m):
        ans = maxpoint(melody[i])
        if ans == -1:
            return -1
        l.append(ans)
    return l

points = points()

if points == -1:
    print(-1)
else:
    for i in range(m):
        print(points[i])

Python: import bisect
import collections
import heapq
import itertools
import math
import string
import sys
from itertools import chain, takewhile


def read(
    f, *shape, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        return f("".join(takewhile(lambda c: c not in whitespaces, it)).strip())

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def main():
    n = read(int)
    weights = []
    values = []
    for i in range(n):
        s, l, p = read(int, 3)
        for j in range(s, l + 1):
            weights.append(j)
            values.append(p)
    m = read(int)
    for _ in range(m):
        W = read(int)
        dp = [0] * 400
        for i in range(len(weights)):
            for w in range(weights[i], W + 1):
                dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
        print(max(dp[0:W+1]))

if __name__ == "__main__":
    main()

Python: def main():
    n = int(input())
    phrase = [tuple(map(int,input().split()))for _ in range(n)]
    m = int(input())
    ans = []
    flag = 1
    dp = [0]*(394)
    for w in range(393):
        for i in range(n):
            t = phrase[i]
            s,l,p = t
            if w+s <= 393:
                dp[w+s] = max(dp[w+s],dp[w]+p)
            if w+l < 393:
                dp[w+l] = max(dp[w+l],dp[w]+p)
            elif w+l >= 393 and w+s < 393:
                dp[393] = max(dp[393],dp[w]+p)
    for _ in range(m):
        w = int(input())
        if not flag:
            continue
        if dp[w]:
            ans.append(dp[w])
        else:
            flag = 0
    if flag:
        for a in ans:
            print(a)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Python: N = int(input())
dp = [-1] * 394
dp[0] = 0

for _ in range(N):
  s,l,p = map(int,input().split())
  for i in range(s, l+1):
    dp[i] = max(dp[i], p)

for i in range(1,394):
  for j in range(i):
    dp[i] = max(dp[i], dp[j]+dp[i-j])

res = []
M = int(input())
for _ in range(M):
  r = dp[int(input())]
  if r == -1:
    print(-1)
    exit()
  else:
    res.append(r)

for r in res: print(r)

Python: def solve():
    from sys import stdin
    f_i = stdin
    
    n = int(f_i.readline())
    
    phrase = [0] * 394
    for i in range(n):
        s, l, p = map(int, f_i.readline().split())
        for i in range(s, l + 1):
            if p > phrase[i]:
                phrase[i] = p

    dp = [0] * 394
    for pl, p in enumerate(phrase[1:], start=1):
        if p:
            for k, t in enumerate(zip(dp, dp[pl:]), start=pl):
                dp_j, dp_k = t
                if dp_j + p > dp_k:
                    dp[k] = dp_j + p
    
    ans = []
    m = int(f_i.readline())
    for i in range(m):
        w = int(f_i.readline())
        if dp[w]:
            ans.append(str(dp[w]))
        else:
            print(-1)
            break
    else:
        print('\n'.join(ans))

solve()

Python: INF = 10 ** 18
N = 393  # フレーズの最大長さ

# phraseの個数
n = int(input())
phrss = [list(map(int, input().split())) for _ in range(n)]
m = int(input())
mldys = [int(input()) for _ in range(m)]

max_mldy = max(mldys)

# mp[i]: 長さiのフレーズの最大の得点
# フレーズごとにforループを回すと遅いから先に長さごとの得点を計算しておく
mp = [-INF] * (N + 1)
for phrase in phrss:
    shortest, longest, point = phrase
    for length in range(shortest, longest + 1):
        mp[length] = max(point, mp[length])

# dp[i]: 長さiのメロディの最大得点
dp = [-INF] * (N + 1)
dp[0] = 0

# DP表更新
for i in range(N + 1):
    for j in range(1, i + 1):
        dp[i] = max(dp[i - j] + mp[j], dp[i])

# OUTPUT
# 答えリスト作成
ans = []
for melody in mldys:
    ans.append(dp[melody])

# メロディにぴったりフレーズを当てはめられるかどうか調べる
# 負の答えがあれば不可能
can = True
for ai in ans:
    if ai < 0:
        can = False

# 答え出力 不可能なら-1を出力
if can:
    for ai in ans:
        print(ai)
else:
    print(-1)

Python: N = int(input())

ph = {}
for i in range(N):
    s,l,p = map(int,input().split())
    for j in range(s,l+1):
        if j not in ph:
            ph[j] = p
        else:
            ph[j] = max(p, ph[j])

M = int(input())
melody = []
for i in range(M):
    melody.append(int(input()))

#print(ph)
phrase = [0 for i in range(393+1)]
for k,p in ph.items():
    for j in range(k,393+1):
        if phrase[j] < phrase[j-k] + p:
            phrase[j] = phrase[j-k] + p

ans = [phrase[i] for i in melody if phrase[i]]
if len(ans) == M:
    [print(i) for i in ans]
else:
    print(-1)