Участник:Ivan mipt/solution1

Материал из DISCOPAL
Перейти к: навигация, поиск

Задача : https://www.codechef.com/problems/RKABOL03

a = raw_input()
while a > 0:
    n = raw_input()
    dp = [[[0 for x in range(n + 1)] for y in range(n + 1)] for z in range(n + 1)]
    cnt = [0] + list(map(int, raw_input().split()))
    ##print(cnt)
    skill = [0] + list(map(int, raw_input().split()))
    ##print(skill)
    g = int(input())
    ans = 0
    for s in range(n + 1):
        for p in range(g + 1):
            for l in range(g + 1):
                dp[s][p][l] = -10000000000000000
    dp[0][0][0] = 0
    for i in range(1, n + 1):
        for j in range(g + 1):
            for k in range(j + 1):
                cur = min(k + cnt[i], g - j)
                for nxt in range(cur + 1):
                    ##print(dp[i][j + nxt][nxt])
                    dp[i][j + nxt][nxt] = max(dp[i][j + nxt][nxt], (dp[i - 1][j][k] + (k + cnt[i] - nxt)*skill[i]));
    for j in range(g + 1):
        for k in range(j + 1):
            ans = max(ans, dp[n][j][k])
            ##print(ans)
    print(ans)
    a = a - 1


StasFomin 09:18, 20 мая 2021 (MSK): Пока ошибка в решении. Пробовал третий и второй питон.

Solution1 2021-05-20 09-18-41 image0.png