Cod sursa(job #990996)

Utilizator yololy97Olaru Bogdan-Ioan yololy97 Data 29 august 2013 13:51:07
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 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) {
        k = i + 2;
        for(j = i + 1; j <= n; ++j) {
            //forul asta nu trebuie sa plece de la j + 1, ci de la cat a ramas anterior
            for(; k <= n && a[i] + a[j] >= a[k]; ++k);//gasim k-ul maxim
            result += (k - 1) - j;
        }
    }

}//bun?da

int main() {
    read();
    solve();
    // sa vedem daca merge... s-ar putea sa fie ceva bushit
    freopen("nrtri.out","w",stdout);
    printf("%d ",result);
}