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: 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 debug(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )

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)
    debug(weights=weights, values=values)
    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: # coding: utf-8
# Your code here!

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]+[-2]*(max_melody) for j in range(n)]

def maxpoint(remin, cache=[lis, 0]):
    dp = cache[0]
    written = cache[1]
    for j in range(n):
        start = max(written - lyric[j][0] + 1, 0)
        stop = remin - lyric[j][0] + 1
        seq_index = ((lyric[j][0]//(lyric[j][1]-lyric[j][0]+1))+1)*lyric[j][0]
        #print("a", j, start, stop, cache)
        for i in range(start, stop):
        #    print("b", j, i, cache)
            if i >= seq_index:
                if j == 0:
                    dp[j][i+lyric[j][0]] = dp[j][i] + lyric[j][2]
                else:
                    dp[j][i+lyric[j][0]] = max(dp[j][i] + lyric[j][2], dp[j-1][i])
            elif dp[j][i] >= 0:
                for k in range(lyric[j][0], min(2*lyric[j][0], lyric[j][1], remin-i)+1):
                    if j == 0:
                        dp[j][i+k] = max(dp[j][i] + lyric[j][2], dp[j][i+k])
                    else:
                        dp[j][i+k] = max(dp[j][i] + lyric[j][2], dp[j][i+k], dp[j-1][i+k])
            else:
                dp[j][i] = -1
        for i in range(stop, remin+1):
            if j == 0:
                dp[j][i] = max(dp[j][i], -1)
            else:
                dp[j][i] = max(dp[j][i], -1, dp[j-1][i])
    written = remin
    return dp[n-1][remin]
        

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: # coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(100000)

def memoize(function):
    def _memoize(*args, _cache={}):
        if args in _cache:
            return _cache[args]
        result = function(*args)
        _cache[args] = result
        return result
    return _memoize

n = int(input())
lyric = [tuple(map(int, input().split(" "))) for i in range(n)]
min_time = min([lyric[i][0] for i in range(n)])
m = int(input())
melody = [int(input()) for i in range(m)]

@memoize
def maxpoint(remin):
    if remin == 0:
        return 0
    elif remin < min_time:
        return -1
    else:
        ans = -1
        for i in range(n):
            for reduc in range(lyric[i][0], lyric[i][1] + 1):
                cand = maxpoint(remin - reduc)
                if cand != -1:
                    ans = max(ans, cand + lyric[i][2])
        return ans

def points():
    lis = []
    for i in range(m):
        p = maxpoint(melody[i])
        if p != -1:
            lis.append(p)
        else:
            return -1
    return lis

l = points()
if l == -1:
    print(-1)
else:
    for p in l:
        print(p)

Python: from collections import defaultdict

max_phrases = defaultdict(int)
n = int(input())
for _ in range(n):
    s, l, p = map(int, input().split())
    for length in range(s, l + 1):
        max_phrases[length] = max(max_phrases[length], p)

m = int(input())
melodies = [int(input()) for _ in range(m)]

max_length = max(melodies)
dp = [-1] * (max_length + max(max_phrases))
dp[0] = 0

for i in range(max_length):
    c = dp[i]
    if c == -1:
        continue
    for length, p in max_phrases.items():
        dp[i + length] = max(dp[i + length], c + p)

results = [None] * m
for i, melody in enumerate(melodies):
    result = dp[melody]
    if result == -1:
        print(-1)
        break
    results[i] = result
else:
    print('\n'.join(map(str, results)))

Python: # coding: utf-8
# Your code here!

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-1) for j in range(n)]

def maxpoint(remin, j = n-1, _cache=lis):
    if remin < 0:
        return -1
    elif _cache[j][remin] is not None:
        return _cache[j][remin]
    else:
        if j >0:
            ans = maxpoint(remin, j-1)
        else:
            ans = -1
        for reduc in range(lyric[j][0], lyric[j][1] + 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):
        l.append(maxpoint(melody[i]-1))
    return l

points = points()

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

Python: n=int(input())
phrase=[tuple(map(int,input().split())) for i in range(n)]
m=int(input())
inf=float('inf')
def main(phrase):
    w=int(input())
    dp=[-1*inf for _ in range(w+1)]
    dp[0]=0
    for i in range(1,w+1):
        for x in phrase:
            s,l,p=x
            for k in range(s,l+1):
                if i-k<0:break
                dp[i]=max(dp[i-k]+p,dp[i])
    return dp[w] if dp[w]>=0 else -1
for i in range(m):
    print(main(phrase))