Lotteria di quadri

Aiuto
1

Save ho ideato questa soluzione per il problema lotteria di quadri e passa tutti i testcase ma solo parte del quinto. Non riesco a capire dove eventualmente sia il problema.

    int quadri(int N, long long M, int V[]){
    int sum = 0;
    int done = 0;
    int range = 0;
    for (range = 0; range < N; range++) {
        sum += V[range];
        if (sum > M) {
            range--;
            break;
        }
    }
    if (range == N) {
        return range;
    }
    while (range >= 0) {
        done = 1;
        //More expensive and alternative solution
        /*for (int j = 0; j < N-range; j++) {
            int s = 0;
            for (int z = j; z < j+range+1; z++) {
                s += V[z];
            }
            if (s > M) {
                range -= 1;
                done = 0;
                break;
            }
        }*/
        int s = 0;
        for (int j = 0; j < range+1; j++) {
            s += V[j];
        }
        for (int z = range+1; z < N; z++) {
            s = s - V[z-(range+1)] + V[z];
            if (s > M) {
                done = 0;
                range -= 1;
                break;
            }
        }
        if (done == 1) {
            break;
        }
    }
    return range+1;
}

Potreste darmi una mano?

2

l’idea di base è buona, devi trovare il modo di ridurre il range mentre scorri il vettore. Non hai bisogno di scorrere due volte la prima parte del vettore.
In pratica il while range>0 non ha senso.

1 Mi Piace
3

Grazie tante per il tuo consiglio. Ho fatto in questa maniera ma mi da gli stessi errori. Non dice che impiega troppo tempo ma che l’output non è corretto.

    int quadri(int N, long long M, int V[]){
    int sum = 0;
    int done = 0;
    int range = 0;
    for (range = 0; range < N; range++) {
        sum += V[range];
        if (sum > M) {
            range--;
            break;
        }
    }
    if (range == N) {
        return range;
    }

    int s = 0;
    for (int j = 0; j < range+1; j++) {
        s += V[j];
    }
    for (int z = range+1; z < N; z++) {
        s = s - V[z-(range+1)] + V[z];
        while (s > M && range >= 0) {
            s -= V[z-range];
            range -= 1;
        }
        if (range == 0) break;
    }
    return range+1;
}
4

Devi utilizzare i long long

5

grazie mille per il consiglio