Каттис Путованье, помогите с ++

Question

Я работаю над проблемой Каттиса Путованье (https://open.kattis.com/problems/putovanje). Я вручную ввел входные данные сэмплов, и выходные данные моей программы соответствуют заданным выходным данным. Но по какой-то причине Каттис принимает мою программу и говорит «Неправильный ответ» в середине проверки моего кода. .

Вот код, который я запускаю для программы:

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int numFruits, numStomach, temp;
    vector<int> fruitWeight;

    cin >> numFruits >> numStomach;

    for (int i = 0; i < numFruits; i++)
    {
        cin >> temp;
        fruitWeight.push_back(temp);
    }

    int edibleFruits = 0;
    int fruitAmount = 0;
    int vecSize = fruitWeight.size();

   for (int i = 0; i< vecSize; i++)
   {
    if (edibleFruits < numStomach)
      {
        edibleFruits += fruitWeight[i];
        fruitAmount++;
      }
    if (edibleFruits > numStomach)
      {
        edibleFruits -= fruitWeight[i];
      }  
    }

 cout << fruitAmount << endl;
 return 0;
}

Я не знаю, почему Каттис не принимает мой ответ и любая помощь высоко ценится!

Спасибо!

Пример ввода 1

5 5
3 1 2 1 1

Пример вывода 1

4

Пример ввода 2

7 5
1 5 4 3 2 1 1

Пример вывода 2

3

Answer 1

Давайте начнем с этой части:

if (edibleFruits < numStomach) {
    edibleFruits += fruitWeight[i];
    fruitAmount++;
}
if (edibleFruits > numStomach) {
    edibleFruits -= fruitWeight[i];
}  

Вы забудете сделать fruitAmount--, когда Милслав переедает. Хотя я бы порекомендовал заменить его на:

if (edibleFruits + fruitWeight[i] <= numStomach) {
    edibleFruits += fruitWeight[i];
    fruitAmount++;
}

Это более компактно.

Следующая часть:

 for (int i = 0; i< vecSize; i++)
   {
    if (edibleFruits < numStomach)
      {
        edibleFruits += fruitWeight[i];
        fruitAmount++;
      }
    if (edibleFruits > numStomach)
      {
        edibleFruits -= fruitWeight[i];
      }  
    }

Вы всегда начинаете есть с первых фруктов и это не всегда оптимально. Вы можете начать есть, начиная с любых фруктов. Например, ввод будет следующим:

3 100
100 50 1

С вашим текущим кодом вы съедите 100 фруктов и пропустите все следующие. Таким образом, ваш ответ будет: 1, а правильный ответ - 2. Потому что вы можете начать есть со второго фрукта и есть 50 и 1.

Самый простой способ решить его - это иметь 2 цикла for, где первый будет перебирать начальный индекс, с которого начнется Milslav есть. И следующий l oop будет повторяться до конца. Максимальное количество фруктов, съеденных общих стартовых показателей, является ответом. Например:

for (int start_eat_from = 0; start_eat_from < N; ++start_eat_from) {
     for (int i = start_eat_from; i < N; ++i) {
     //Eat everything if Milslav can and check that he ate the maximum amount.
     }
}

Это сработает, потому что будет только 10^6 итераций, и оно будет завершено за 1 секунду.

Если N больше, чем оно было бы необходимо использовать некоторое динамическое программирование.

UPD:

В целом код будет выглядеть так:

for (int start_from = 0; start_from < numFruits; ++start_from) {
        edibleFruits = 0;
        int tmpFruitAmount = 0;
        for (int i = start_from; i < numFruits; ++i) {
            if (edibleFruits + fruitWeight[i] <= numStomach) {
                edibleFruits += fruitWeight[i];
                tmpFruitAmount++;
            }
        }
        fruitAmount = max(fruitAmount, tmpFruitAmount);
    }