Cod sursa(job #2611879)

Utilizator Horia14Horia Banciu Horia14 Data 7 mai 2020 19:20:28
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include<cstdio>
#include<algorithm>
#define MAX_N 800
using namespace std;

int v[MAX_N+1], n, ans;

void read() {
    FILE* fin = fopen("nrtri.in","r");
    fscanf(fin,"%d",&n);
    for(int i = 1; i <= n; i++)
        fscanf(fin,"%d",&v[i]);
    fclose(fin);
}

int binarySearch(int Begin, int End, int val) {
    int mid, b = Begin, e = End, pos = -1;
    while(b <= e) {
        mid = (b + e) >> 1;
        if(v[mid] <= val) {
            pos = mid;
            b = mid + 1;
        } else e = mid - 1;
    }
    return pos;
}

void solve() {
    FILE* fout = fopen("nrtri.out","w");
    int i, j, p;
    for(i = 1; i <= n; i++)
        for(j = i + 1; j <= n; j++) {
            p = binarySearch(j+1,n,v[i]+v[j]);
            if(p != -1)
                ans += p - j;
        }
    fprintf(fout,"%d\n",ans);
    fclose(fout);
}

int main() {
    read();
    sort(v+1,v+n+1);
    solve();
    return 0;
}