Submission #23947600

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import sys
input = sys.stdin.readline
def main():
    w, n = map(int, input().split())
    p = [tuple(map(int, input().split())) for _ in range(n)]
    p.sort(key=lambda x: x[1] - x[0])
    inf = 1 << 60
    dp = [-inf for _ in range(w + 1)]
    dp[0] = 0
    ans = -inf
    for l, r, v in p:
        ans = max(ans, max(dp[w - r: w - l + 1]) + v)
        for i in range(w, l - 1, -1):
            dp[i] = max(dp[i], dp[i - l] + v)
            if i >= r:
                dp[i] = max(dp[i], dp[i - r] + v)
    print(ans if ans > 0 else -1)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import sys

input = sys.stdin.readline


def main():
    w, n = map(int, input().split())
    p = [tuple(map(int, input().split())) for _ in range(n)]
    p.sort(key=lambda x: x[1] - x[0])
    inf = 1 << 60
    dp = [-inf for _ in range(w + 1)]
    dp[0] = 0
    ans = -inf
    for l, r, v in p:
        ans = max(ans, max(dp[w - r: w - l + 1]) + v)
        for i in range(w, l - 1, -1):
            dp[i] = max(dp[i], dp[i - l] + v)
            if i >= r:
                dp[i] = max(dp[i], dp[i - r] + v)

    print(ans if ans > 0 else -1)


if __name__ == "__main__":
    main()

Submission Info

Judge Result