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.

Hi Codeforces!
I'm still a beginner here—just started recently. In this short journey, I made a few small mistakes. Sharing them here in case it helps someone else who’s new like me.

1. Solving problems by looking at tags
In the beginning, I didn't know how to approach problems, so I used tags. Now I realize it's better to think by myself and struggle a bit—that's how real learning happens.

2. Ignoring editorials
When I got WA, I used to get frustrated. Now I read editorials, try to understand the solution, and then solve again. It helps a lot.

3. Random practice
I used to solve problems without a plan. Now I try to practice by rating—like only solving 800–1000 rated problems for a few days.

4. Giving up too quickly
I used to feel like “I can't do this.” But now I know everyone learns step by step. Consistency matters.

Final Note:

I'm still learning. If you’ve made similar mistakes or have any tips, feel free to share in the comments.

— @Abdul_Alim