Pagini recente » Cod sursa (job #1896982) | Cod sursa (job #1763981) | Cod sursa (job #2699102) | Cod sursa (job #1853710) | Cod sursa (job #1480240)
#include <cstdio>
const char iname[] = "nrtri.in";
const char oname[] = "nrtri.out";
const int MAXN = 805;
int n, a[MAXN], b[MAXN];
void read(){
freopen(iname, "r", stdin);
scanf("%d", &n);
for(int i = 0; i < n; ++i)
scanf("%d", a+i);
}
void merge_sort(int st, int dr){
if(st != dr){
int mid = (st + dr) >> 1;
merge_sort(st, mid);
merge_sort(mid+1, dr);
for(int i = st, k = st, j = mid+1; j<=dr || i <= mid;)
if((j>dr) || ((i<=mid) && (a[i] < a[j])))
b[k++] = a[i++];
else
b[k++] = a[j++];
for(int i = st; i <= dr; ++i)
a[i] = b[i];
}
}
int lowBound(int p, int q){
int lo, hi, mid;
int x = a[p], y = a[q];
for(lo = q+1, hi = n-1, mid = lo + ((hi - lo) >> 1); lo < hi; mid = lo +((hi - lo) >> 1)){
if(x+y >= a[mid]){
if((x+a[mid] >= y) && (y+a[mid] >= x)) hi = mid;
else lo = mid + 1;
}
else hi = mid-1;
}
if((!(x+y>=a[lo]))||(!(x+a[lo] >= y)) || (!(y+a[lo] >= x)))
return -1;
return lo;
}
int uppBound(int p, int q){
int x = a[p], y = a[q];
int lo, hi, mid;
for(lo = q+1, hi = n-1, mid = lo + ((hi-lo+1) >> 1); lo < hi; mid = lo + ((hi-lo+1)>>1)){
if(x+y < a[mid])
hi = mid - 1;
else if((x+a[mid] >= y) && (y+a[mid]>=x)) lo = mid;
else lo = mid + 1;
}
if(x+y < a[lo]) return -1;
return lo;
}
void solve(){
int ans = 0;
for(int i = 0; i < n-1; ++i)
for(int j = i+1; j < n; ++j){
int pozMin = lowBound(i,j);
if((pozMin >= 0) && (pozMin != j) && (pozMin != i)){
int pozMax = uppBound(i, j);
if(pozMax != j && pozMax != i){
ans += pozMax - pozMin + 1;
}
}
}
freopen(oname, "w", stdout);
printf("%d", ans);
}
int main()
{
read();
merge_sort(0,n-1);
solve();
return 0;
}