Cod sursa(job #2070697)

Utilizator MaligMamaliga cu smantana Malig Data 19 noiembrie 2017 20:32:06
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
#include <algorithm>

#if 1
#define pv(x) cout<<#x<<" = "<<x<<"; ";cout.flush()
#define pn cout<<endl
#else
#define pv(x)
#define pn
#endif

using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");

#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
const int NMax = 5e4 + 50;
const int sMax = 25e4 + 5;
typedef pair<int,int> point;

int N,M;
int v[NMax];

int main() {
    in>>N;

    for (int i=1;i <= N;++i) {
        in>>v[i];
    }

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

    int ans = 0;
    for (int i=1;i <= N;++i) {
        for (int j=i+1;j <=  N;++j) {

            int pw = 1;
            for(;pw <= N;pw <<= 1) ;
            pw >>= 1;

            int pos = j;
            while (pw) {
                if (pos + pw <= N && v[pos+pw] <= v[i] + v[j]) {
                    pos += pw;
                }

                pw >>= 1;
            }

            ans += pos - j;
        }
    }

    out<<ans<<'\n';

    return 0;
}