# Almost there! Execution timed out

**URL:** <https://forum.olinfo.it/t/almost-there-execution-timed-out/8112>\
**Category:** Aiuto\
**Created:** [12 Marzo 2023, 8:39pm UTC](https://forum.olinfo.it/t/almost-there-execution-timed-out/8112 "2023-03-12T20:39:48Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![ByteBusters](https://forum.olinfo.it/user_avatar/forum.olinfo.it/bytebusters/32/2470_2.png) [@ByteBusters](https://forum.olinfo.it/u/ByteBusters)\
**Post date:** [12 Marzo 2023, 8:39pm UTC](https://forum.olinfo.it/t/almost-there-execution-timed-out/8112/1 "2023-03-12T20:39:48Z")

</div>

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:

```auto
#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;
}

```

---

<div class="post-metadata">

**Author:** ![fve5](https://forum.olinfo.it/user_avatar/forum.olinfo.it/fve5/32/3229_2.png) [@fve5](https://forum.olinfo.it/u/fve5)\
**Post date:** [13 Marzo 2023, 6:51am UTC](https://forum.olinfo.it/t/almost-there-execution-timed-out/8112/2 "2023-03-13T06:51:31Z")

</div>

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.