Cod sursa(job #1480258)

Utilizator dorumusuroiFMI - Doru Musuroi dorumusuroi Data 2 septembrie 2015 12:53:15
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#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;
}