Pagini recente » Cod sursa (job #1347987) | Cod sursa (job #2749719) | Cod sursa (job #1906691) | Cod sursa (job #23712) | Cod sursa (job #1480258)
#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];
}
}
void solve(){
int ans = 0;
for(int i = 0; i < n-2; ++i)
for(int j = i+1; j < n - 1; ++j){
int l = j, r = n-1, mid;
int s = a[i] + a[j];
while(l != r){
mid = l + ((r-l+1) >> 1);
if(s >= a[mid]) l = mid;
else r = mid-1;
}
ans += (l - j);
}
freopen(oname, "w", stdout);
printf("%d", ans);
}
int main()
{
read();
merge_sort(0,n-1);
solve();
return 0;
}