Official Analysis (Java)

Explanation

We run a knapsack DP with the weights of the fruits and a capacity of $T$. To handle the drinking of water, we take half the weight of each valid state and mark those states as valid as well. Finally, we can run another knapsack DP based on the halved weights.

Implementation

Time Complexity: $\mathcal{O}(T)$, where $T$ is the maximum fullness.

Copy
with open("feast.in") as fin:
	max_fullness, orange, lemon = map(int, fin.readline().split())

# dp[i][0] is no water; dp[i][1] is water used
dp = [[False, False] for _ in range(max_fullness + 1)]
dp[0][0] = True

# First knapsack: no water states and initial halved states
for i in range(max_fullness + 1):
	if dp[i][0]:

Alternative Explanation

Instead of a knapsack solution, a BFS/DFS can be done to iterate though all attainable states and determine the one with maximum fullness. The scene can be thought of as a graph by defining each edge to be the transition from fullness $i$ to $j$. Each state is defined by fullness and whether Bessie has drank water. There are thus $2T$ states, and each state is visited at most once.

Implementation - BFS

Time Complexity: $\mathcal{O}(T)$, where $T$ is the maximum fullness.

Copy
from collections import deque

with open("feast.in") as fin:
	max_fullness, orange, lemon = map(int, fin.readline().split())

# visited[i][0] is water unused; visited[i][1] is water used
visited = [[False, False] for _ in range(max_fullness + 1)]
visited[0][0] = True

# (fullness, water)

Implementation - DFS

Time Complexity: $\mathcal{O}(T)$, where $T$ is the maximum fullness.

Copy
from sys import setrecursionlimit

setrecursionlimit(1 << 25)

with open("feast.in") as fin:
	max_fullness, orange, lemon = map(int, fin.readline().split())

# visited[i][0] is water unused; visited[i][1] is water used
visited = [[False, False] for _ in range(max_fullness + 1)]