Cod sursa(job #3135224)

Utilizator profinfo114Prof Info profinfo114 Data 2 iunie 2023 13:49:04
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("nrtri.in");
ofstream fout ("nrtri.out");

const int NM = 1e3 + 5;

long long sum = 0;
int n, a[NM];

int main(){
  fin >> n;
  for (int i = 1; i <= n; i++){
    fin >> a[i];
  }
  sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; i++){
    for (int j = i + 1; j <= n; j++){
      int l = j + 1, r = n, ans = j;
      while (l <= r){
        int mid = (l + r) / 2;
        if (a[i] + a[j] >= a[mid]){
          ans = max(ans, mid);
          l = mid + 1;
        }
        else{
          r = mid - 1;
        }
      }
      sum += ans - j;
    }
  }
  fout << sum;
}