Cod sursa(job #2923998)

Utilizator Alex18maiAlex Enache Alex18mai Data 22 septembrie 2022 19:03:14
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

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

vector <int> v;

int main() {

    int n;
    cin>>n;

    v.resize(n);
    for (int i=0; i<n; i++){
        cin>>v[i];
    }
    sort(v.begin(), v.end());

    int sum = 0;

    for (int i=0; i<n; i++){
        //tehnica: 2 pointers
        int k = i+1;
        for (int j=i+1; j<n; j++){
            //i si j fixate
            //k creste pe masura ce j creste deoarece v[j+1] >= v[j]
            while (k < n && v[k] <= v[i] + v[j]){
                k++;
            }
            //k o sa fie elementul unde nu se mai pastreaza proprietatea (din acest motiv scadem 1)
            sum += k-j-1;
            //cout<<"Pentru : I="<<i<<" si J="<<j<<" o sa fie bune toate elementele intre "<<j+1<<" "<<k-1<<'\n';
        }
    }

    cout<<sum<<'\n';

    return 0;
}