# Lotteria di quadri (quadri) \[Execution Timed Out\]

**URL:** <https://forum.olinfo.it/t/lotteria-di-quadri-quadri-execution-timed-out/5985>\
**Category:** Aiuto\
**Created:** [26 Dicembre 2019, 10:00am UTC](https://forum.olinfo.it/t/lotteria-di-quadri-quadri-execution-timed-out/5985 "2019-12-26T10:00:35Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![guglielmo.boi](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/ebca7d/32.png) [@guglielmo.boi](https://forum.olinfo.it/u/guglielmo.boi)\
**Post date:** [26 Dicembre 2019, 10:00am UTC](https://forum.olinfo.it/t/lotteria-di-quadri-quadri-execution-timed-out/5985/1 "2019-12-26T10:00:35Z")

</div>

Ciao, qualcuno mi potrebbe dare un suggerimento? Immagino che l’algoritmo che ho trovato (il più semplice?) non sia abbastanza efficiente.

```auto
int quadri(int N, long long M, int V[]) {
    int B = 1;

    while(true){
        long long sum = 0;
        for(int i = 0; i < B; ++i){
            sum += V[i];
        }

        for(int i = 0; i < N - B; ++i){
            sum -= V[i];
            sum += V[i + B];

            if(sum > M){
                return --B;
            }
        }

        ++B;
    }

    return -1;
}

```

---

<div class="post-metadata">

**Author:** ![Doxeno](https://forum.olinfo.it/user_avatar/forum.olinfo.it/doxeno/32/648_2.png) [@Doxeno](https://forum.olinfo.it/u/Doxeno)\
**Post date:** [26 Dicembre 2019, 1:19pm UTC](https://forum.olinfo.it/t/lotteria-di-quadri-quadri-execution-timed-out/5985/2 "2019-12-26T13:19:27Z")

</div>

Prima di tutto ci sono degli errori, cioè che qualora M fosse maggiore della somma dei valori dei quadri la funzione ripeterebbe il loop all’infinito senza mai ritornare un valore, per evitare questo basta mettere dei limiti a B, come `while(B <= N)`  
Inoltre non controlli se la somma dei primi B elementi sia maggiore di M, fai il controllo solo per i sottoinsiemi successivi e nel caso in cui nessuna sottosequenza fosse maggiore di M dovresti restituire N, non - 1.  
In secondo luogo, la tua soluzione è in `O(N^2)`, mentre per rientrare nel tempo limite del problema è necessaria una soluzione al più in `O(NlogN)`.  
Se ti interessa, ci sono soluzioni sia in `O(NlogN)` che in `O(N)`, le lascio in spoiler qui sotto.  
`O(NlogN)`:Binary Search  
`O(N)`:Sliding Window