Avrei bisogno di una mano per ottimizzare il mio programma:
int i,n,s,j,k;
int V[10000000];
int main()
{
in=fopen("input.txt","r");
out=fopen("output.txt","w");
fscanf(in,"%d\n",&n);
for(i=0;i<n;i++)
fscanf(in,"%d\n",&V[i]);
sort(V,V+n);
for(i=0;i<n-2;i++)
{
j=i+1;
while(j<n-1)
{
k=j+1;
while(V[i]+V[j]>=V[k] && k<n) k++;
s=s+(n-k);
j++;
}
}
fprintf(out,"%d",s);
return 0;
}Ciao,
il codice che hai messo è incompleto (forse Discourse se ne è mangiato un pezzo). Prova a rimetterlo all’interno del tag apposito (attivabile dalla barra degli strumenti mentre si sta scrivendo) in modo che risulti leggibile.
Inoltre, se non è il codice in senso stretto ad avere problemi, è meglio che tu descriva a parole l’idea risolutiva che hai seguito. 
L’idea era quella di ordinare le lunghezze dei lati e iniziare a sommare i primi due poi il primo e il terzo ecct. finchè non trovavi che con uno dei lati successivi formava un triangolo impossibile e quindi tutti i successivi erano a loro volta impossibili dopodichè reiterare sommando secondo e terzo secondo e quarto e così via.
Spero di essere stato più chiaro possibile 
Provo a spiegare formalmente quanto hai scritto (correggimi se ho interpretato male):
per ogni coppia (i, j) provi tutti i k finché una terna (i, j, k) non può formare un triangolo.
A quel punto hai notato correttamente (osservazione fondamentale) che se (i, j, k) non forma un triangolo allora nessuna terna (i, j, k') con k' > k può formare un triangolo.
Stimiamo la complessità computazionale del tuo algoritmo:
Come vedi, la complessità del tuo algoritmo è ancora N^3, insufficiente per risolvere gli ultimi subtask.
Puoi immaginare di riuscire a trovare il k più piccolo, data una coppia, con una complessità inferiore a N?
L’idea che mi è venuta è quella di partire dalla metà del vettore delle lunghezze in modo da ridurre la complessità in alcuni casi a N/2 ma i subtask continuano a darmi Execution timed out, documentandomi ho trovato la possibilità di usare la funzione binary_search per trovare un numero in un vettore, è possibile utilizzarla anche per confrontare?
Non direttamente, ma è possibile fare qualcosa di simile con lower_bound e upper_bound.
Sei sulla strada giusta
Utilizzando upper_bound i subtask 3 (gli ultimi 3) in cui mi dava Execution timed out ora mi da Output isn’t correct mentre la subtask 4 continua ad andare fuori tempo.
Risolvere il subtask 4 richiede un algoritmo N^2 mentre adesso stiamo progettando un algoritmo N^2logN, quindi è corretto che sia fuori tempo.
Per il subtask 3 ti ricordo che per ogni coppia (i, j) devi cercare il più piccolo k per cui (i, j, k) non forma un triangolo. Se ti sembra di aver fatto ciò, puoi mettere il codice e vediamo cosa non va.
Il contatore s può eccedre 2^{31}-1. Usa un intero lungo al posto di un intero semplice.
Perfetto dopo tanta fatica il subtask 3 è finalmente corretto ora però visto che sei così gentile ti chiedo un suggerimento per impostare la risoluzione del problema con complessità N².
La base del ragionamento è sempre la stessa: supponendo che i numeri siano ordinati, per ogni (i, j) devi trovare il più piccolo k per cui (i, j, k) non forma un triangolo.
Considera due coppie (i, j_1) e (i, j_2) con j_1 < j_2. È semplice osservare che k_2 (inteso come il k di cui sopra per la terna (i, j_2, k_2)) sarà sicuramente maggiore di k_1 (in (i, j_1, k_1)).
Ciò significa che se iteri su j devi solo controllare i numeri a partire dal k precedente che hai trovato.
Dal punto di vista della complessità computazione, per ogni i non impieghiamo mai più di N passaggi, il che ci porta a un algoritmo O(N^2).
Ora solo l’ultimo dei casi del subtask 4 va fuori tempo massimo ma questo credo che sia un mio problema. Ti lascio il link del nuovo programma così puoi controllarlo:
Il tuo codice mi pare esegua ancora N^2 volte una ricerca binaria con upper_bound…
Resta quindi una complessità di N^2logN.
La soluzione N^2 non prevede l’uso della ricerca binaria.