This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <algorithm>
#include <vector>
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vll::iterator vlli;
int main() {
int n;scanf("%d",&n);
vll a(n,0);
for(int i=0;i<n;i++){
long long tmp;
scanf("%lld",&tmp);a[i]=tmp;
}
sort(a.begin(),a.end());
vll psum(n,0);
psum[0]=a[0];
for(int i=1;i<n;i++)psum[i]=(psum[i-1]+a[i])%MOD;
vll ppsum(n,0);
for(int i=n-2;i>=0;i--){
vlli hi= upper_bound(a.begin(),a.end(),a[i]);
int idx=hi-a.begin();
if(idx==n)ppsum[i]=ppsum[i+1];
else{ppsum[i]=(ppsum[i+1]+(a[i]*((MOD+psum[n-1]-psum[idx-1])%MOD))%MOD)%MOD;}
//printf("%lld %lld ",a[i],psum[n-1]-psum[idx-1]);
}
ll ans=0;
for(int i=0;i<n;i++){
vlli hi= upper_bound(a.begin(),a.end(),a[i]);
int idx=hi-a.begin();
//printf("%d\n",idx);
if(idx==n)continue;
ans=(ans+(a[i]*ppsum[idx])%MOD)%MOD;
}
//for(int i=0;i<n;i++)printf("%lld ",ppsum[i]);
printf("%lld\n",ans);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |