Cod sursa(job #2132295)

Utilizator ioanaa_ghGhiorghi Ioana-Cristina ioanaa_gh Data 15 februarie 2018 17:41:28
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int n, a[3005], i, j, cnt, s, st, dr, mij;
int main()
{
  fin >> n;
  for(i = 1 ; i <= n ; i++)
    fin >> a[i];
  sort(a + 1 , a + n + 1);
  for(i = 1 ; i <= n-2 ; i++)
  {
    for(j = i + 1 ; j <= n-1 ; j++)
      {
        s = a[i] + a[j];
        st = j + 1;
        dr = n;
        while(st <= dr)
        {
            mij = (st + dr) / 2;
            if(s >= a[mij])
                st = mij + 1;
            else dr = mij - 1;
        }
        cnt = cnt + dr - j;
      }
  }
    fout << cnt;

    fin.close();
    fout.close();

    return 0;
}