Cod sursa(job #1681012)

Utilizator dsergiu05Sergiu Druga dsergiu05 Data 9 aprilie 2016 11:07:49
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <fstream>

using namespace std;

ifstream fin("nrtri_2.in");
ofstream fout("nrtri_2.out");

const int nmax=800;
int v[nmax+1], v2[nmax+1];

void mergesort(int l, int r) {
    if (l==r) {
        return;
    } else {
        mergesort(l,(r+l)/2);
        mergesort((r+l)/2+1,r);
        int i=l, j=(r+l)/2+1, k=l;
        while (i<=(r+l)/2 || j<=r) {
            if (i>(l+r)/2) {
                v2[k]=v[j];
                j++;
            } else if (j>r) {
                v2[k]=v[i];
                i++;
            } else if (v[i]<v[j]) {
                v2[k]=v[i];
                i++;
            } else {
                v2[k]=v[j];
                j++;
            }
            k++;
        }
        for (int i=l; i<=r; i++) {
            v[i]=v2[i];
        }
    }
}

int main () {
    int n;
    fin>>n;

    int n2;
    for (int n2=1; n2<=n/2; n2*=2) {
    }

    for (int i=1; i<=n; i++) {
        fin>>v[i];
    }
    mergesort(1,n);

    int sol=0;
    for (int i=1; i<=n-2; i++) {
        for (int j=i+1; j<=n-1; j++) {
            int k=j;
            for (int step=n2; step>=1; step/=2) {
                if (k+step<=n && v[k+step]<=v[i]+v[j]) {
                    k+=step;
                }
            }
            sol+=k-j;
        }
    }

    fout<<sol<<"\n";

    return 0;
}