# Aiuto per Lotteria di quadri (abc\_quadri)

**URL:** <https://forum.olinfo.it/t/aiuto-per-lotteria-di-quadri-abc-quadri/9370>\
**Category:** Aiuto\
**Created:** [15 Gennaio 2025, 11:02pm UTC](https://forum.olinfo.it/t/aiuto-per-lotteria-di-quadri-abc-quadri/9370 "2025-01-15T23:02:05Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![Zuthy0](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/z/48db29/32.png) [@Zuthy0](https://forum.olinfo.it/u/Zuthy0)\
**Post date:** [15 Gennaio 2025, 11:02pm UTC](https://forum.olinfo.it/t/aiuto-per-lotteria-di-quadri-abc-quadri/9370/1 "2025-01-15T23:02:05Z")

</div>

Ciao a tutti, ho bisogno di aiuto per risolvere il problema [Lotteria di quadri](https://training.olinfo.it/task/abc_quadri).  
output corretti ma molti vanno in time limit exceed, come posso ottimizzare il codice  
20/100

Ecco il mio codice:  
#include   
#include   
using namespace std;

int quadri(int N, long long M, int l) {  
vectorV(N);  
for(int i=0;i\<N;i++) {  
V[i]=l[i];  
}  
int B=N;  
long long sum=0;  
for(int j=0;j\<N;j++) {  
for(int i=0;i\<=j;i++) {  
sum=accumulate(V.begin()+i,V.end()-j+i,0);  
if(sum\>M) {  
B–;  
break;  
}  
}  
}  
return B;  
}

Grazie mille in anticipo!

---

<div class="post-metadata">

**Author:** ![LeoJ](https://forum.olinfo.it/user_avatar/forum.olinfo.it/leoj/32/2737_2.png) [@LeoJ](https://forum.olinfo.it/u/LeoJ)\
**Post date:** [18 Gennaio 2025, 9:35am UTC](https://forum.olinfo.it/t/aiuto-per-lotteria-di-quadri-abc-quadri/9370/2 "2025-01-18T09:35:47Z")

</div>

Ciao, questo problema l’ho risolto un po’ di tempo fa e quindi proverò ad aiutarti e se non capisci qualcosa prova ad approfondire su internet.  
Come hai notato il tuo codice fa TLE, questo è dovuto alla sua complessità temporale che se non erro è O(N^3): te hai implementato due cicli for annidati (complessità di O(N^2) con al suo interno std::accumulate (O(N)) → O(N ^ 2) \* O(N) = O(N ^ 3).

Una complessità cubica con N che può arrivare a 200 000 non è fattibile (se provi a fare 200 000 ^ 3 fa 8.000.000.000.000.000, un numero di operazioni troppo grande: tieni conto che il limite di tempo è 0.3 secondi e in un secondo si eseguono circa 10^8 operazioni…).

> **tecnica da utilizzare**
>
> Se vuoi risolvere questo problema ti consiglio di guardare la tecnica “sliding window” (finestra scorrevole): [Tecnica della finestra scorrevole - GeeksforGeeks](https://www.geeksforgeeks.org/window-sliding-technique/).

Questa tecnica permette la risoluzione in tempo lineare (O(N)) di molti problemi che richiedono di trovare il massimo / minimo subarray che rispetti determinate condizioni.  
Dopo aver risolto quadri puoi allenarti ancora su questa tecnica sul problema [Training - Christmas Lights (olinfo.it)](https://training.olinfo.it/task/ois_lights), che è molto simile.  
P.s. per incollare del codice usa l’opzione “testo preformattato” (il simbolo \</\> )

---

<div class="post-metadata">

**Author:** ![Zuthy0](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/z/48db29/32.png) [@Zuthy0](https://forum.olinfo.it/u/Zuthy0)\
**Post date:** [22 Gennaio 2025, 6:11pm UTC](https://forum.olinfo.it/t/aiuto-per-lotteria-di-quadri-abc-quadri/9370/3 "2025-01-22T18:11:49Z")

</div>

non riesco lo stesso ho provato a fare la sliding windows come mi hai detto tu e fatto anche un altro controllo, come posso risolvere?

```auto
#include <numeric>
#include <vector>
using namespace std;

int quadri(int N, long long M, int l[]) {
   vector<int>V(N);
   for(int i=0;i<N;i++) {
      V[i]=l[i];
   }
   int B=N;
   int temp=0;
   long long sum=0;
   int a=0,b=0;

   for(int j=0;j<N;j++) {
      temp=0;
      sum=accumulate(V.begin(),V.begin()+B,0);
      for(int i=0;i<=j;i++) {
         if(sum>M) {
            B--;
            break;
         }
         sum-=V[i];
         sum+=V[i+B];
         temp++;
      }
      if(temp==j+1)return B;
   }
   return B;
};

```

---

<div class="post-metadata">

**Author:** ![Zuthy0](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/z/48db29/32.png) [@Zuthy0](https://forum.olinfo.it/u/Zuthy0)\
**Post date:** [22 Gennaio 2025, 7:19pm UTC](https://forum.olinfo.it/t/aiuto-per-lotteria-di-quadri-abc-quadri/9370/4 "2025-01-22T19:19:03Z")

</div>

ok ho risolto il mio problema , grazie mille 🙂

---

<div class="post-metadata">

**Author:** ![robompolo](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/r/2bfe46/32.png) [@robompolo](https://forum.olinfo.it/u/robompolo)\
**Post date:** [23 Gennaio 2025, 1:44am UTC](https://forum.olinfo.it/t/aiuto-per-lotteria-di-quadri-abc-quadri/9370/5 "2025-01-23T01:44:28Z")

</div>

Ciao, scrivo non per il problema lotteria di quadri ma piuttosto per chiedere aiuto riguardo a come poter scrivere messaggi: è da mezzora che cerco di capire come fare ma non trovo il modo (sono solo riuscito a rispondere a messaggi già esistenti come sto facendo ora), non è che qualcuno potrebbe dirmi come posso fare? grazie mille

---

<div class="post-metadata">

**Author:** ![LeoJ](https://forum.olinfo.it/user_avatar/forum.olinfo.it/leoj/32/2737_2.png) [@LeoJ](https://forum.olinfo.it/u/LeoJ)\
**Post date:** [23 Gennaio 2025, 2:45pm UTC](https://forum.olinfo.it/t/aiuto-per-lotteria-di-quadri-abc-quadri/9370/6 "2025-01-23T14:45:18Z")

</div>

Ok, se intendi creare nuovi post per chiedere informazioni, farsi aiutare o condividere qualcosa su un problema, devi solo andare nella homepage del forum e clicchi l’opzione “crea nuovo argomento” e, dopo aver selezionato le varie info del post (se è un aiuto oppure chiarimento o una segnalazione…) scrivi quello che devi scrivere e aspetti per delle risposte…  
Spero tu abbia capito

 ![Screenshot (203)](https://forum.olinfo.it/uploads/default/original/2X/0/0ced2c0d75cb3b48cb6c0aa8b2c75badf3713490.jpeg)

---

<div class="post-metadata">

**Author:** ![robompolo](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/r/2bfe46/32.png) [@robompolo](https://forum.olinfo.it/u/robompolo)\
**Post date:** [23 Gennaio 2025, 4:20pm UTC](https://forum.olinfo.it/t/aiuto-per-lotteria-di-quadri-abc-quadri/9370/7 "2025-01-23T16:20:15Z")

</div>

![Screenshot 2025-01-23 171908](https://forum.olinfo.it/uploads/default/original/2X/e/e4737ba5e2c257b562895927b5f1e2159b18e146.png)  
non me lo da il tasto che posso fare?

---

<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:** [23 Gennaio 2025, 5:21pm UTC](https://forum.olinfo.it/t/aiuto-per-lotteria-di-quadri-abc-quadri/9370/8 "2025-01-23T17:21:10Z")

</div>

Riprova ora.

---

<div class="post-metadata">

**Author:** ![robompolo](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/r/2bfe46/32.png) [@robompolo](https://forum.olinfo.it/u/robompolo)\
**Post date:** [23 Gennaio 2025, 6:27pm UTC](https://forum.olinfo.it/t/aiuto-per-lotteria-di-quadri-abc-quadri/9370/9 "2025-01-23T18:27:25Z")

</div>

adesso me lo da ti ringrazio!