Cod sursa(job #2299540)

Utilizator bananamandaoneTudor Cosmin Oanea bananamandaone Data 9 decembrie 2018 18:11:21
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include<algorithm>
#include<fstream>
#include<iostream>

using namespace std;

ifstream fin("bete2.in");
ofstream fout("bete2.out");

int n,v[3003];

int main()
{
    int i,j,t,sol=0;
    fin>>n;
    for(i=1; i<=n; i++)
        fin>>v[i];

    sort(v+1, v+n+1);
    for(i = 1; i + 2 <= n ; i++)
    {
        ///presupunem ca l-am ales pe i+1;
        t = i + 2;
        for (j = i + 1; j + 1 <=n; j++)
        {
            while (t + 1 <= n && v[i] + v[j] >= v[t + 1])
                t++;	/// t se duce pana cand (!(v[i] + v[j] < v[t])) , adica la primul t pentru care v[i] + v[j] >= v[t];
            if (v[i] + v[j] <= v[t])
                sol += t-j+1;
        }
    }
    fout<<sol<<"\n";

    fin.close();
    fout.close();
    return 0;
}