Oral exam (threshold) @ 70 / 100

Aiuto
1

Salve a tutti,
Ho creato una soluzione per risolvere il problema “Threshold” delle ois2018…
Purtroppo ottengo solo 70 / 100 per via di un “Execution timed out” nell’ ultimo subtask…
Qui c’è il mio codice:
long long N;
int number;
int k[100 + 1] { 0 };

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    scanf("%d", &N);
    for(int i = 0; i < N; i++) {
        scanf("%d", &number);
        for(int j = 0; j <= number; j++)
            k[j]++;
    }
    for(int i = 100; i >= 0; i--)
        printf("%d ", k[i]);
    return 0;
}

Sapete aiutarmi ?

2

Sei sicuro che devi fare l’update per ogni valore , potresti incrementare l’array k in modo più efficiente.

1 Mi Piace
3

Del tipo ? Tu che mi consigli ?

4

O non incrementarlo proprio :smile:

1 Mi Piace
5

Cioè ? Non capisco che vuol dire “non incrementarlo proprio”

6

Ipotizza che:nel momento in cui ricevi un valore v incrementi solo k[v] , riesci a capire tramite i valori contenuti in k quanti valori superiori ci sono di quello in considerazione?

È uno spreco incrementare casella per casella tutte le n volte.

1 Mi Piace