Cod sursa(job #1971404)

Utilizator sichetpaulSichet Paul sichetpaul Data 20 aprilie 2017 13:25:35
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <fstream>
#include <algorithm>
using namespace std;
int v[801];
int main()
{ int n,i,j,nr=0,st,dr,mij,Max;
    ifstream f("nrtri.in");
    ofstream g("nrtri.out");
    f>>n;
    for (i=1;i<=n;++i)
        f>>v[i];
    sort(v+1,v+n+1);
    for (i=1;i<=n-2;++i)
    for (j=i+1;j<=n-1;++j) {
        st=j+1;
        dr=n;
        Max=0;
        while (st<=dr) {
           mij=(st+dr)/2;
           if (v[mij]<=v[i]+v[j]) {
              st=mij+1;
              Max=max(Max,mij-j);
           }
           else dr=mij-1;
        }
        nr+=Max;
    }
      g<<nr;
    return 0;
}