Cod sursa(job #1981119)

Utilizator Alex18maiAlex Enache Alex18mai Data 14 mai 2017 20:26:25
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 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 st=j+1;
            int dr=n;
            int sol=-1;
            while (st<=dr){
                int mij=(st+dr)/2;
                if (A[i]+A[j]<=A[mij]){
                    st=mij+1;
                    sol=mij;
                }
                else{
                    dr=mij-1;
                }
            }
            if (sol!=-1){
                s+=sol-j;
            }
        }
    }
    cout<<s;
    return 0;
}