Mai intai trebuie sa te autentifici.
Cod sursa(job #2324543)
Utilizator | Data | 20 ianuarie 2019 23:00:00 | |
---|---|---|---|
Problema | Numarare triunghiuri | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.96 kb |
#include <cstdio>
#include <cassert>
#include <vector>
#include <algorithm>
using namespace std;
int plz[1005];
int given[1005];
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);
assert(n <= 800);
plz[1] = 1;
given[1000] = 133742;
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){
assert(j <= n);
assert(i <= n);
int left = j + 1, right = n, mid, last = j;
while(left <= right){
mid = (left + right) >> 1;
assert(mid <= n);
if(given[i] + given[j] >= given[mid]){
last = mid;
left = mid + 1;
}
else
right = mid - 1;
}
ans += last - j;
}
printf("%d", ans);
return 0;
}