Cod sursa(job #1976450)

Utilizator RaresEGaySopterean Adrian RaresEGay Data 3 mai 2017 14:35:22
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <fstream>
#include <algorithm>

#define MAXN 805

using namespace std;

ifstream f ("nrtri.in");
ofstream g ("nrtri.out");

int n, v[MAXN];
int sum;

int main(){
    f >> n;
    for(int i = 1; i <= n; ++i) f >> v[i];

    sort(v + 1, v + 1 + n);

    for(int i = 1; i <= n - 2; ++i){
        for(int j = i + 1; j <= n - 1; ++j){
            int lo = j, hi = n;
            int target;
            while(lo <= hi){
                int mid = (lo + hi) / 2;
                if(v[mid] <= v[i] + v[j]){
                    lo = mid + 1;
                    target = mid;
                }
                else hi = mid - 1;
            }
            sum += target - j;
        }
    }

    g << sum << '\n';
}