Cod sursa(job #1059486)

Utilizator nytr0gennytr0gen nytr0gen Data 16 decembrie 2013 18:56:32
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <cstdio>
using namespace std;

const int Nmax = 801;

int main() {
    int n, x, i, j, st, dr, m;
    int v[Nmax];

    freopen("nrtri.in", "r", stdin);
    freopen("nrtri.out", "w", stdout);

    scanf("%d", &n);
    for (i = 1; i <= n; ++i) {
        scanf("%d", &x);
        for (j = i-1; x < v[j] && j > 0; --j) {
            v[j+1] = v[j];
        }
        v[j+1] = x;
    }

    for (x = 0, i = 1; i <= n; ++i) {
        for (j = i+1; j <= n; ++j) {
            st = j+1;
            dr = n;
            while (dr >= st) {
                m = st+(dr-st)/2;
                if (v[i]+v[j] >= v[m]) {
                    if (   v[m]+v[i] >= v[j]
                        && v[m]+v[j] >= v[i]
                    ) {++x;}
                    st = m+1;
                } else {
                    dr = m-1;
                }
            }
        }
    }

    printf("%d\n", x);

    return 0;
}