accumulate_long_long.cpp

/**
* Example:
* - Grades:   2 4 2 6 1 7 8 9 2 1
* - Candies:  1 2 1 2 1 2 3 4 2 1
* 
* Look for the longest strictly increasing & decreasing sequence?
*/
long long min_candies(std::vector<long long> const& grades)
{
    int n = grades.size();
    std::vector<long long> candies(n, 1);
    
    int start = 0;
    while (start < n)
    {
        int top = start; //find the top of the hill
        while (top < n - 1 && grades[top + 1] > grades[top]) ++top;
        
        int bot = top; //find the bottom of the hill
        while (bot < n - 1 && grades[bot + 1] < grades[bot]) ++bot;
        
        // Filling the candies increasingly until reaching the top of the hill, then decreasing toward the bottom
        for (int i = start; i < top; ++i)
            candies[i] = i - start + 1;
        candies[top] = 1 + std::max(top - start, bot - top);
        for (int i = top + 1; i <= bot; ++i)
            candies[i] = 1 + bot - i;

        start = top != bot
            ? bot
            : top + 1;
    }
    
    // The long long forced conversion is absolutely necessary to avoid overflow
    return std::accumulate(candies.begin(), candies.end(), static_cast<long long>(0), std::plus<long long>());
}