Cod sursa(job #1346628)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 18 februarie 2015 14:41:25
Problema Numarare triunghiuri Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <cstdio>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <cstring>
#include <string>
#include <set>
#include <stack>
#include <deque>
#define pb push_back

#define mp make_pair
#define f first
#define s second
#define ll long long

using namespace std;

const int MaxVal = 30005;

int main() {
#ifndef ONLINE_JUDGE
  ifstream cin("nrtri.in");
  ofstream cout("nrtri.out");
#endif
  int N; cin >> N;
  vector <int> v(N);
  vector <int> freq(MaxVal, 0);
  for (int i = 0; i < N; ++i) {
    cin >> v[i];
    freq[v[i]] += 1;
  }
  for (int i = 1; i < MaxVal; ++i) {
    freq[i] += freq[i - 1];
  }
  int answer = 0;

  sort(v.begin(), v.end());
  for (int i = 0; i < N - 1; ++i) {
    for (int j = i + 1; j < N; ++j) {
      int many = 1;
      while(j < N && v[j + 1] == v[j]) {
        ++j;
        many += 1;
      }
      answer += (freq[v[i] + v[j]] - freq[v[j]]) * many;
    }
  }
  cout << answer << "\n";
  return 0;
}