TÓPICO

Time limit exceeded

Arimario Jesus perguntou 10 months ago

O meu código sempre tem resposa Time limit exceeded, sendo que o Timelimit do problema é de 3 e o runtime do meu código é de 3.000 (ou seja, no limite).

Código abaixo:

system("cls");
do{
    scanf("%d", &N);
}while((N<0) || (N>pow(10, 6)));
do{
    scanf("%d", &M);
}while((M<2) || (M>pow(10, 9)));

int S[N+2];
S[0]=1;
S[N+1]=M;
for(i=1; i<=N; i++){
    do{
        scanf("%d", &S[i]);
    }while((S[i]<=S[i-1]) || (S[i]==S[i-1]) || (S[i]>=M));
}

do{
    scanf("%d", &X);
}while(X<1);
do{
    scanf("%d", &Y);
}while((Y<=X) || (Y>pow(10, 9)));

for(i=0; i<N+1; i=j){
    g_over=0;
    for(j=N+1; j>i; j--){
        if(!flag){
            if((S[j]-S[i])<=Y){
                Jumps++;
                flag=1;
                break;
            }
        }
        if((S[j]-S[i])<=X){
            Jumps++;
            flag=0;
            break;
        }else g_over++;
    }
    if(g_over==((N+1)-i)){
        Jumps=-1;
        break;
    }
}

printf("%d\n", Jumps);

return 0;

}

Lembre de não publicar soluções. Sua publicação pode ser revisada por nossos moderadores.

  • feodorv respondido 10 months ago

    system("cls");

    Please, do not use system in OJ solutions.

    do{
        scanf("%d", &N);
    }while((N<0) || (N>pow(10, 6)));
    do{
        scanf("%d", &M);
    }while((M<2) || (M>pow(10, 9)));
    

    You can trust the input data and use simple

    scanf( "%d %d", &N, &M);

    As for the TLE.

    for(i=0; i<N+1; i=j){
        for(j=N+1; j>i; j--){

    N can be up to 10^6 and you have N^2 algorithm so 10^12 operations give TLE. You should find other approaches to the problem (O(N) or O(NlogN) in complexity).

  • Arimario Jesus respondido 10 months ago

    Thanks FEODORV!