Cod sursa(job #2324493)

Utilizator cruelifanLouis Cypher cruelifan Data 20 ianuarie 2019 21:01:38
Problema Numarare triunghiuri Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int given[1005];

inline bool cmp(int &x, int &y){
  return x <= y;
}

int main(){
  freopen("nrtri.in", "r", stdin);
  freopen("nrtri.out", "w", stdout);

  int n;
  scanf("%d", &n);

  for(int i = 1; i <= n; ++i)
    scanf("%d", &given[i]);

  sort(given + 1, given + n + 1, cmp);

  int ans = 0;
  for(int i = 1; i <= n; ++i)
    for(int j = i + 1; j <= n; ++j){
      int left = j + 1, right = n, mid, last = j;
      while(left <= right){
        mid = left + (right - left) / 2;
        if(given[i] + given[j] >= given[mid]){
          last = mid;
          left = mid + 1;
        }
        else
          right = mid - 1;
      }
      ans += last - j;
    }

  printf("%d", ans);

  return 0;
}