Salve a tutti,
Qualche giorno fa ho provato a risolvere il problema “ois_grattacieli”…
Nonostante il codice sia giusto, ottengo 70/100 per via di due Execution Timed Out nell’ultimo subtask…
Qui potete trovare il mio codice : https://pastebin.com/bRS9hkTc.
Grazie 
Ciao,
nel tuo codice per ogni grattacielo ti calcoli il numero di grattacieli che riesci a vedere, quindi la complessità diventa \mathcal O(N^2) che con N=10^5 va fuori tempo, prova a pensare ad un modo per risolvere il problema in \mathcal O(N).
Hint:
il massimo numero di grattacieli che puoi ammirare si ottiene da uno dei grattacieli più alti.
Per farlo mi conviene modificare il ciclo principale giusto ?
L’algoritmo non è sbagliato, è solo troppo lento, quindi se vuoi fare 100/100 devi cambiare approccio e con “cambiare approccio” intendo rifarlo da capo.
Prova a concentrarti su questa osservazione:
se sono sul grattacielo più alto la visuale può essere ostacolata solo da grattacieli alti uguali.
Ho ottenuto 100/100 senza riscrivere il codice ma aggiungendo un semplice if.
int osserva(int N, int H[]) { int l, r, S=0, M=*std::max_element(H,H+N); for(int i=0; i<N; i++) { if(H[i] == M) { for(l=max(0, i-1); l>0 && H[l]<H[i]; l--); for(r=min(N-1,i+1); r<N-1 && H[r]<H[i]; r++); S = max(r-l+1, S); } } return S; }
In effetti la tua soluzione funziona perché la somma delle visuali dei grattacieli più alti è 2N.
Comunque tu continui a calcolarti la visuale in \mathcal O(N) e io cercavo di farti trovare un modo per farlo in \mathcal O(1), ma se funziona così lascio perdere 