Cod sursa(job #2617733)

Utilizator pascustefanPascu Stefan Liviu pascustefan Data 22 mai 2020 18:18:55
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <bits/stdc++.h>
#include <fstream>
using namespace std;

ifstream f("nrtri.in");
ofstream g("nrtri.out");
int v[810];

void quick_sort(int v[], int s, int d) {
    int i, j, i1, j1, c, k;
    if (s < d) {
        i = s;
        j = d;
        i1 = 0;
        j1 = -1;
        while (i < j) {
            if (v[i] > v[j]) {
                c = v[i];
                v[i] = v[j];
                v[j] = c;
                c = i1;
                i1 = -j1;
                j1 = -c;
            }
            i = i + i1;
            j = j + j1;
        }
        k=i;
        quick_sort(v, s, k - 1);
        quick_sort(v, k + 1, d);
    }
}

int main()
{
    int i, j, k, n, nr;
    nr = 0;
    f>>n;
    for(i = 0; i < n; i++)
        f>>v[i];
    quick_sort(v, 0, n - 1);
    for(i = 0; i < n - 2; i++)
    {
        k = i + 2;
        for(j = i + 1; j < n - 1; j++)
        {
            while(v[i] + v[j] >= v[k] && k < n)
                k++;
            if(k>j)
                nr = nr + k - j - 1;
        }
    }
    g<<nr;
    return 0;
}