Pagini recente » Cod sursa (job #1545332) | Cod sursa (job #2881621) | Cod sursa (job #1107922) | Cod sursa (job #1851309) | Cod sursa (job #930539)
Cod sursa(job #930539)
#include <cstdio>
#include <algorithm>
#define NMax 30001
using namespace std; long n,vmin[NMax+NMax],v[NMax],minn,maxx,rez; int bsearchMin(long in,long fn,long v[],long val) { long mid; if(v[fn]<=val) return fn; else if(val<v[1]) return 0; while(in<fn) { mid=(fn-in)/2+in+1; if(val<v[mid]) fn=mid-1; else in=mid; } return fn; } bool comp(long a,long b) { if(a<=b) return 1; return 0; } int main() { freopen("nrtri.in","rt",stdin); freopen("nrtri.out","wt",stdout); scanf("%ld",&n); for(long i=1;i<=n;i++) scanf("%ld",&v[i]); sort(v+1,v+n+1,comp); for(long i=0;i<=NMax+NMax;i++) { vmin[i]=bsearchMin(1,n,v,i); } for(long i=1;i<n;i++) for(long j=i+1;j<=n;j++) { maxx=vmin[v[j]+v[i]]; rez+=maxx-j > 0 ? maxx-j : 0; } printf("%ld\n",rez); return 0; }