Pagini recente » Cod sursa (job #37180) | Cod sursa (job #1966433) | Cod sursa (job #2109270) | Cod sursa (job #407058) | Cod sursa (job #2923998)
#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;
}