Almost there! Execution timed out

Ciao a tutti!
Vi chiedo un aiuto con questo problema: “Episodio I: un acquisto difficile (acquisti)” aka “oii_acquisti”.

Per qualche centesimo di secondo non passo tutti i test, ma ottengo execution timed out.

Sono abbastanza sicuro che logicamente la funzione sia corretta, non sò però come ottimizzare la sua velocità.

Ecco il codice:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<long long> calcola(int T, int M, vector<long long> S, vector<long long> P) {
    vector<long long> result(M, 0);

    for (int suitecase = 0; suitecase < M; suitecase++) {
        long long toReach = P[suitecase];
        for (int i = 0; i < T; i++) {
            long long xi;
            if (i == 0) {
                xi = S[i];
            } else {
                if (toReach / i >= 0)
                    xi = min(S[i], toReach / i);
                else
                    break;
            }
            result[suitecase] += xi;
            toReach -= xi * i;
        }
    }
    return result;
}

Ciao, quando il tuo programma supera il tempo limite, viene killato dal sistema e il tempo che viene visualizzato è solo poco sopra il tempo limite, indipendentemente da quanto effettivamente ci avrebbe messo se l’avessero lasciato terminare.
La tua soluzione itera su tutte le valigie e per ogni valigia su tutti i souvenir, quindi ha complessità \mathcal{O}(MT) che per questo task è troppo alta. Per ottimizzare considera la possibilità di ordinare l’array delle valigie o di fare una binsearch per trovare il numero di souvenir esauriti.