Pagini recente » Cod sursa (job #190287) | Cod sursa (job #627205) | Cod sursa (job #1150491) | Cod sursa (job #1077220) | Cod sursa (job #927797)
Cod sursa(job #927797)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
#define Nmax 40002
char FileIn [] = { "nrtri.in" };
char FileOut [] = { "nrtri.out" };
int N, R;
int V[Nmax], Vmin[Nmax];
void citire(){
ifstream f(FileIn);
f >> N;
for ( int i = 1; i <= N; ++i )
f >> V[i];
f.close();
}
int cautare ( int st, int dr, int x ) {
int m;
if ( V[dr] <= x )
return dr;
else
if ( x < V[1] )
return 0;
while ( st <= dr ) {
m = (dr - st) / 2 + st;
if ( V[m] <= x && x < V[m + 1] )
return m;
else
if ( x < V[m])
dr = m - 1;
else
st = m + 1;
}
return 0;
}
void rezolva(){
for ( int i = 0; i <= Nmax + Nmax; i++ )
Vmin[i] = cautare ( 1, N, i );
for ( int i = 1; i < N; i++ )
for ( int j = i + 1; j <= N; j++ ) {
int maxim = Vmin[ V[i] + V[j] ];
R += max ( maxim - j, 0 );
}
}
void afis(){
ofstream g(FileOut);
g << R << "\n";
g.close();
}
int main(){
citire();
sort ( V + 1, V + N + 1 );
rezolva();
afis();
return 0;
}