Cod sursa(job #744313)

Utilizator padreatiAurelian Tutuianu padreati Data 8 mai 2012 13:03:23
Problema Numarare triunghiuri Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <stack>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <string.h>

using namespace std;

void sol();

int main() {
#ifdef PADREATI
    freopen("in.txt", "r", stdin);
#else
    freopen("nrtri.in", "r", stdin);
    freopen("nrtri.out", "w", stdout);
#endif
    sol();
    return 0;
}

#define N 801
#define LEN 30001

int n;
int v[N];
int cnt[LEN];

int cmp(const void *o1, const void *o2) {
    return *(int*) o1 - *(int*) o2;
}

void sol() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &v[i]);
    for (int i = 0; i < LEN; i++) cnt[i] = 0;
    for (int i = 0; i < n; i++) cnt[v[i]]++;
    for (int i = 1; i < LEN; i++) cnt[i] += cnt[i - 1];
    qsort(v, n, sizeof (int), cmp);
    int t = 0;
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            int val = cnt[v[i]] - cnt[v[j] - v[i] - 1] - 1;
            if (v[i] == v[j])val--;
            if (v[i] > v[j] - v[i]) t += val > 0 ? val : 0;
        }
    printf("%d\n", t);
}