Pagini recente » Cod sursa (job #2753047) | Cod sursa (job #2061085) | Cod sursa (job #2446548) | Monitorul de evaluare | Cod sursa (job #334938)
Cod sursa(job #334938)
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
int poz[60001];
int ap[60001];
int cnt[60001];
vector<int> nrs;
int main()
{
ifstream f("nrtri.in");
ofstream g("nrtri.out");
int sol=0,n,i,j,x;
f>>n;
for(i=0;i<n;i++) {f>>x; nrs.push_back(x);}
make_heap(nrs.begin(),nrs.end());
sort_heap(nrs.begin(),nrs.end());
for(i=0;i<n;i++) {if(!poz[nrs[i]]) poz[nrs[i]]=i+1; ap[nrs[i]]++;}
for(i=1;i<=60000;i++)
{ if(poz[i])
cnt[i]=cnt[i-1]+ap[i];
else cnt[i]=cnt[i-1];
}
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
sol+=cnt[nrs[i]+nrs[j]]-cnt[nrs[j]];
if(j-poz[nrs[j]]+2<=ap[nrs[j]])
sol+=ap[nrs[j]]-j+poz[nrs[j]]-2;
}
g<<sol;
f.close();
g.close();
return 0;
}