Problema Fette di Strudel


#1

Sto facendo il problema Fette di Strudel ma ottengo 70/100 perchè solo nel testcase n°026 il mio programma va fuori tempo massimo. Mi potreste dare qualche consiglio per velocizzare il codice?

#include <bits/stdc++.h>

using namespace std;

#pragma Gcc optimize("Ofast")

#define MAXN 100001

int porziona(int N, int mandorle[], int cannella[]) {
    int sum[N];
    sum[0]=cannella[0]-mandorle[0];
    for(int i=1;i<N;i++){
        sum[i]=sum[i-1]+cannella[i]-mandorle[i];
    }
    for(int lung=N;lung>1;lung--){
        if(sum[lung-1]>0)
            return lung;
        int pos=lung;
        while(pos<N){
            if(sum[pos]-sum[pos-lung]>0)
                return lung;
            pos++;
        }
    }
    return 1;
}


int mandorle[MAXN], cannella[MAXN];

int main() {
    FILE *fr, *fw;
    int N, i;

    fr = fopen("input.txt", "r");
    fw = fopen("output.txt", "w");
    assert(1 == fscanf(fr, "%d", &N));
    for(i=0; i<N; i++)
        assert(1 == fscanf(fr, "%d", &mandorle[i]));
    for(i=0; i<N; i++)
        assert(1 == fscanf(fr, "%d", &cannella[i]));

    fprintf(fw, "%d\n", porziona(N, mandorle, cannella));
    fclose(fr);
    fclose(fw);
    return 0;
}

#2

La tua soluzione ha una complessita’ di O(N^2), N e’ al massimo 100000, percui e’ normale che non stia nei tempi.
Per prendere 100 senza rubarlo ti conviene trovare una soluzione con complessita’ migliore.
hint: puoi risolverlo modificando poco il tuo codice con complessita’ O(NlogN)
hint: si puo’ risolvere con complessita’ O(N)