Cod sursa(job #1990644)

Utilizator SpiristulTeribilStefan Vilcu SpiristulTeribil Data 12 iunie 2017 20:55:43
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std ;

ifstream cin ("nrtri.in") ;
ofstream cout ("nrtri.out") ;

int main () {
    int n ; 
    cin >> n ;
    vector <int> v (n) ; 
    for (int i = 0 ; i < n ; ++ i) {
        cin >> v [i] ;
    }
    sort (v.begin(), v.end()) ;
    int ans = 0 ;
    for (int i = 0 ; i < n ; ++ i) {
        for (int j = i + 1 ; j < n ; ++ j) {
            int st = j + 1 ; 
            int dr = n - 1 ; 
            int sol = j ; 
            while (st <= dr) {
                int mij = (st + dr) >> 1 ;
                if (v[mij] <= v [i] + v [j]) {
                    st = mij + 1 ; 
                    sol = mij ;
                }
                else {
                    dr = mij - 1 ;
                }
            }
            ans = ans + sol - j ;
        }
    }
    cout << ans ;
    return 0 ; 
}