oj.uz

Submission #2402

# Submission time Handle Problem Language Result Execution time Memory
2402 2013-07-21T07:50:47 Z alephnull 지우개 (GA4_eraser) C++
0 / 100
 28 ms 2568 KB 
#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]+1);
		int idx=hi-a.begin()-1;
		if(a[idx]==a[i])ppsum[i]=ppsum[i+1];
		else{ppsum[i]=(ppsum[i+1]+(a[i]*((MOD+psum[n-1]-psum[idx-1])%MOD))%MOD)%MOD;}
	}
	ll ans=0;
	for(int i=0;i<n;i++){
		vlli hi= upper_bound(a.begin(),a.end(),a[i]+1);
		int idx=hi-a.begin()-1;
		//printf("%d\n",idx);
		if(a[idx]==a[i])continue;
		ans=(ans+(a[i]*ppsum[idx])%MOD)%MOD;

	}
	//for(int i=0;i<n;i++)printf("%lld ",ppsum[i]);
	printf("%lld\n",ans);
}

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 912 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 912 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 912 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 912 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 2568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 2568 KB Output isn't correct
2 Halted 0 ms 0 KB -