Cod sursa(job #1981125)

Utilizator Alex18maiAlex Enache Alex18mai Data 14 mai 2017 20:41:00
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream cin("nrtri.in");
ofstream cout("nrtri.out");

int A[803];

int main()
{
    int n;
    cin>>n;
    int s=0;
    for (int i=1; i<=n; i++){
        cin>>A[i];
    }
    sort (A+1, A+n+1);
    for (int i=1; i<=n; i++){
        for (int j=i+1; j<=n; j++){
            int sol = 0 ;
            for (int step = 1 << 10 ; step > 0; step >>= 1){
                if (sol + step <= n and A [i] + A [j] >= A [sol + step]) {
                    sol += step ;
                }
            }
            if (sol){
                s+=sol-j;
            }
        }
    }
    cout<<s;
    return 0;
}