Cod sursa(job #990990)

Utilizator yololy97Olaru Bogdan-Ioan yololy97 Data 29 august 2013 13:40:34
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
// fac eu sortarea
#include <cstdio>
#include <algorithm>

using namespace std;

int a[801];
int n;
int result;

void read() {
    freopen ("nrtri.in", "r", stdin);
    scanf ("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf ("%d", &a[i]);
}

void solve() {
    sort(a + 1, a + n + 1);

    int i, j, k;
    // continua tu
    for(i = 1; i <= n; ++i)
        for(j = i + 1; j < n; ++j) {
            // cauti binar pe k folosind puteri ai lui 2
            // pracctic determini fiecare bit al rezultatului
            int cnt;
            for (k = j + 1, cnt = (1 << 10); cnt; cnt /= 2)
                if (k + cnt <= n && a[i] + a[j] >= a[k + cnt])
                    k += cnt;
            if (a[i] + a[j] >= a[k])
                result += k - j;
        }
        

}//bun?da

int main() {
    read();
    solve();
    freopen("nrtri.out","w",stdout);
    printf("%d ",result);
}