Pagini recente » Cod sursa (job #756503) | Cod sursa (job #1818164) | Cod sursa (job #2584639) | Cod sursa (job #1918259) | Cod sursa (job #793983)
Cod sursa(job #793983)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream ifs("nrtri.in");
ofstream ofs("nrtri.out");
int search(int x);
vector <int> v;
int N;
int result=0;
int main(){
ifs>>N;
v.resize(N);
for(int i=0;i<N;i++)
ifs>>v[i];
sort(v.begin(),v.end());
for(int i=N-1;i>=2;i--){
for(int n=i-1;n>=0;n--){
int s=search(v[i]-v[n]);
if(s>=n) break;
else result+=n-s;
}
}
ofs<<result;
return 0;
}
//index of the first element in v that is >=x. Using some crippled binary search.
inline int search(int x){
int min=0,max=N;
int pivot;
while(max>=min){
pivot=(max+min)/2;
if(x>v[pivot])
min=pivot+1;
else if(x<v[pivot])
max=pivot-1;
else
return pivot;
}
return pivot;
}