Cod sursa(job #1493597)

Utilizator tudorcomanTudor Coman tudorcoman Data 29 septembrie 2015 17:45:17
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb

#include <algorithm>
#include <stdio.h>
#include <assert.h>

const int maxN = 2005;
const int maxVal = 30000;
const char *in = "nrtri.in";
const char *out = "nrtri.out";
int v[maxN];

int main() {
    assert(freopen(in, "r", stdin));
    assert(freopen(out, "w", stdout));

    int n, answer = 0;
    scanf("%d",&n);
    for(register int i = 1; i <= n; ++ i)
        scanf("%d",&v[i]);

    std::sort(v + 1, v + n + 1);
    for(register int i = 1; i <= n; ++ i) {
        int last = i + 1;
        for(int j = i + 1; j <= n; ++ j) {
            while(last < j || (last < n and v[i] + v[j] > v[last + 1])) {
                ++ last;
            }
            answer += last - j;
        }
    }

    printf("%d\n", answer);
    return 0;
}