import sys
input = sys.stdin.readline
n, m, k = map(int, input().split())
pref = []
for _ in range(n):
a = list(map(int, input().split()))
p = [0] * (m + 1)
for i in range(m):
p[i+1] = p[i] + a[i]
pref.append(p)
dp = [0] * (k + 1)
for i in range(n):
ndp = dp[:]
for w in range(1, m + 1):
for j in range(k, w - 1, -1):
ndp[j] = max(ndp[j], dp[j - w] + pref[i][w])
dp = ndp
print(dp[k])
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | import sys input = sys.stdin.readline n, m, k = map(int, input().split()) pref = [] for _ in range(n): a = list(map(int, input().split())) p = [0] * (m + 1) for i in range(m): p[i+1] = p[i] + a[i] pref.append(p) dp = [0] * (k + 1) for i in range(n): ndp = dp[:] for w in range(1, m + 1): for j in range(k, w - 1, -1): ndp[j] = max(ndp[j], dp[j - w] + pref[i][w]) dp = ndp print(dp[k]) |
English