Cod sursa(job #1662509)

Utilizator CalarisPredut Denis Stefanita Calaris Data 24 martie 2016 20:06:22
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <fstream>
#include <algorithm>
#include <iostream>

using namespace std;

#define MAX 801
#define ll long long

void citire();
void afisare(ll);
ll rezolvare();
int sir[MAX],N;

int main()
{
    citire();
    afisare(rezolvare());
    return 0;
}

void citire()
{
  fstream f("nrtri.in",ios::in);
  int x,i;
  f>>N;
  for(i=0;i<N;++i)f>>x, sir[i]=x;
};

void afisare(ll ans)
{
  ofstream g("nrtri.out");
  g<<ans;
}

ll rezolvare()
{
  sort(sir,sir+N);
  ll ans=0;
  int i,j,first,second,t;
  for(i=0;i<=N-3;++i)
    {
    for(j=i+1;j<=N-2;++j)
        {
         first=j+1;
         second=N-1;
         t=(first+second)/2;
         while(first<=second)
            {
            t=(first+second)/2;
            if(sir[i]+sir[j]<sir[t])second = t-1;
            else first=t+1;
            }
         ans+=second-j;
        }
    }
    return ans;
}