Lotteria di quadri (quadri)

Aiuto
1

Ciao, ho provato a risolvere l’esercizio “Lotteria di quadri” e passa tutti i testcase ma solo in parte il quinto. Dichiarando s (la mia somma) come int mi dice che l’output non è corretto, se invece la dichiaro long long, quei casi dove prima mi dava output non corretto adesso vado fuori tempo. Avete consigli? Grazie in anticipo.

int quadri(int N, long long M, int V[]) {
    int b=0, c, i, j=0;
    long long s=0;
    bool modificato=false;
    
    for(i=0; i<N; i++) {
    	s += V[i];
    	if(s>M) {
    		modificato=true;
    		break;
		} 
    	b++;
	}
	if(modificato==false) return b;
    
    for(int i=1; i<N; i++) {
    	c=0;
    	s=0;
		j=i;
		modificato=false;
    	for(int j=i; j<N; j++) {
    		s += V[j];
			if(s>M) {
				modificato=true;
    			break;
			}
    		c++;
		}
		if(b>c && modificato) b=c;
		else {
			if(modificato==false) break;
		}
	}
    return b;
}
2

Devi diminuire la complessità della tua soluzione che al momento è O(N^2), la soluzione più intuitiva sfrutta la ricerca binaria per ottenere complessità O(NlogN), ma esiste anche una soluzione lineare.

Per quanto riguarda i long long sono necessari per evitare overflow.

2 Mi Piace