Cod sursa(job #2020028)

Utilizator dianamariaDiana Cataros dianamaria Data 9 septembrie 2017 12:07:44
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in ("nrtri.in");
ofstream out ("nrtri.out");
vector<int>v;
int main()
{
    int n,ind,x,i,j,ans=0;
    in>>n;
    for (i=0;i<n;i++)
        in>>x, v.push_back(x);
    sort(v.begin(),v.end());
    for (i=0;i<n-1;i++)
        for (j=i+1;j<n-1;j++)
        {
            if (v[n-1]<=v[i]+v[j])
                ans+=n-j-1;
            else
            {
                vector<int>::iterator it;
                it=upper_bound(v.begin()+j,v.end(),v[i]+v[j]);
                ind=(int)(it-(v.begin()+j));
                ans+=ind-1;
            }
        }
    out<<ans;
    return 0;
}