Cod sursa(job #2769281)

Utilizator UnknownPercentageBuca Mihnea-Vicentiu UnknownPercentage Data 14 august 2021 15:03:26
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <bits/stdc++.h>
 
using namespace std;

ifstream f("nrtri.in");
ofstream g("nrtri.out");
 
short int F[30001];

int v[800];
 
int main() {
    int N, mx = 0;
    f >> N;
 
    for(int i = 1, x;i <= N;i++) {
        f >> x, F[x]++;
        mx = max(mx, x);
    }
 
    N = 0;
    for(int i = 1;i <= mx;i++)
        while(F[i] > 0) {
            v[++N] = i, F[i]--;
        }
 
    long long cnt = 0;
    for(int i = N;i >= 2;i--) {
        int l = 1, r = i - 1;
        while(l < r) {
            if(v[l] + v[r] >= v[i]) {
                cnt += r - l;
                r--;
            } else l++;
        }
    }
 
    g << cnt;
}