Cod sursa(job #2633613)
Utilizator | Data | 7 iulie 2020 21:53:54 | |
---|---|---|---|
Problema | Numarare triunghiuri | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.58 kb |
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin ("nrtri.in");
ofstream fout ("nrtri.out");
int n, cnt, a[805];
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 - 2; i ++)
for (int j = i + 1 ; j < n; j ++) {
int st = j + 1, dr = n , k = n;
while (st <= dr) {
k = (st + dr) / 2;
if (a[i] + a[j] >= a[k])
st = k + 1;
else
dr = k - 1;
}
cnt += (dr - j);
}
fout << cnt;
return 0;
}