Cod sursa(job #2064562)

Utilizator GhiciCineRazvan Dumitriu GhiciCine Data 12 noiembrie 2017 15:22:14
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.59 kb
#include <cstdio>
#include <algorithm>
#define MAXN 800

using namespace std;

int v[MAXN + 5];

int main( ) {
  int n, i, j, p, nrtri;

  freopen( "nrtri.in", "r", stdin );
  freopen( "nrtri.out", "w", stdout );

  scanf( "%d", &n );
  for( i = 0; i < n; i++ )
    scanf( "%d", &v[i] );
  sort( v, v + n );
  nrtri = 0;
  for( i = 0; i < n - 2; i++ ) {
    p = i + 2;
    for( j = i + 1; j < n - 1; j++ ) {
      if( j == p )
        p++;
      while( p < n && v[i] + v[j] >= v[p] )
        p++;
      nrtri += p - j - 1;
    }
  }
  printf( "%d", nrtri );
  return 0;
}