Cod sursa(job #1990856)

Utilizator theoioanaTheodoraD theoioana Data 13 iunie 2017 22:12:07
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int n, v[802], i, j, minn, aux, p, k, st, dr, mid, sol;

int main(){

         fin>>n;

         for(i=1;i<=n;i++)
                  fin>>v[i];
         for(i=1;i<n;i++){
                  minn=v[i];
                  p=i;
                  for(j=i+1;j<=n;j++)
                  if(minn>v[j]){
                           minn=v[j];
                           p=j;
                  }
                  aux=v[i];
                  v[i]=v[p];
                  v[p]=aux;
         }
         for(i=1;i<=n-2;i++)
         for(j=i+1;j<=n-1;j++){
                  st=j;
                  dr=n;
                  while(st<=dr){
                           mid=(st+dr)/2;

                           if(v[mid]>v[i]+v[j])
                                    dr=mid-1;
                           else
                                    st=mid+1;
                  }

                           if(v[dr]<=v[i]+v[j])
                                    sol+=dr-j;
         }
         fout<<sol;


}