Hello everyone,

I’m working on the USACO 2015 December Gold problem Fruit Feast. The goal is to find the maximum fullness Bessie can achieve by eating two types of fruits, with an option to drink water once which halves her fullness.

Problem Summary

Maximum fullness T (1 ≤ T ≤ 5,000,000)

Eating an orange adds A fullness, a lemon adds B fullness (1 ≤ A,B ≤ T)

Bessie can eat fruits any number of times without exceeding fullness T

Bessie can drink water once, which halves fullness (floor division)

Find the maximum achievable fullness

My Approach and Code

I used a DP array dp to track achievable fullness states. Also, I use a boolean track array to record if water has been used or not at each state.

dp[i] == true means fullness i is achievable.

track[i] == true means water has not been used at fullness i.

track[i] == false means water has already been used at fullness i.

Whenever I move from fullness i to i + v[j] by eating a fruit, if water is still available (track[i] == true), I mark (i + v[j]) / 2 as reachable (drinking water now), and mark water as used there.

Here’s my code (without file I/O for simplicity):-

#include <bits/stdc++.h>
using namespace std;

#define ll long long

void solve()
{
    ll t;
    vector<ll> v(3, 0);
    cin >> t >> v[1] >> v[2];

    vector<bool> dp(t + 1, false), track(t + 1, true);
    dp[0] = true;

    for (ll i = 0; i <= t; i++)
    {
        for (ll j = 1; j <= 2; j++)
        {
            if (dp[i] && i + v[j] <= t)
            {
                dp[i + v[j]] = true;
                if (track[i])
                {
                    dp[(i + v[j]) / 2] = true;
                    track[(i + v[j]) / 2] = false;
                }
            }
        }
    }

    for (ll i = t; i >= 0; i--)
    {
        if (dp[i])
        {
            cout << i << endl;
            return;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

My Question

My code passes almost all test cases, but fails test case #11 on the USACO judge.

I suspect it has to do with how I update dp and use the track array.

Is there a flaw in the way I handle transitions or water usage?

Can this failure be fixed without completely changing my code structure?

Any hints or explanations about why test case 11 fails would be really appreciated! Thanks in advance.