Cod sursa(job #3139021)

Utilizator BurloiEmilAndreiBurloi Emil Andrei BurloiEmilAndrei Data 24 iunie 2023 11:04:31
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <fstream>
#include <algorithm>
using namespace std;

ifstream cin("nrtri.in");
ofstream cout("nrtri.out");

const int MAXN = 2000;

int lat[MAXN];

int main() {
    int n, i, j, k, ans;

    cin >> n;
    for(i = 0; i < n; i++){
        cin >> lat[i];
    }
    sort(lat, lat + n);
    ans = 0;
    for(i = 0; i <= n - 3; i++){
        j = i + 2;
        for(k = i + 1; k <= n - 2; k++){
            // lat[j] > lat[i]  | =>                           lat[j] + lat[k] > lat[i]   |
            // lat[k] > lat[i]  |                                                         |  => lat[i] + lat[j] > lat[k] => merge
            while(j < n && lat[i] + lat[k] >= lat[j]) ++j; //   lat[i] + lat[k] > lat[j]   |
            ans += j - k - 1;
        }
    }
    cout << ans;
    return 0;
}