oj.uz

Submission #2404

# Submission time Handle Problem Language Result Execution time Memory
2404 2013-07-21T08:04:26 Z alephnull 지우개 (GA4_eraser) C++
100 / 100
 40 ms 3192 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]);
		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);
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 912 KB Output is correct
2 Correct 0 ms 912 KB Output is correct
3 Correct 0 ms 912 KB Output is correct
4 Correct 0 ms 912 KB Output is correct
5 Correct 0 ms 912 KB Output is correct
6 Correct 0 ms 912 KB Output is correct
7 Correct 0 ms 912 KB Output is correct
8 Correct 0 ms 912 KB Output is correct
9 Correct 0 ms 912 KB Output is correct
10 Correct 0 ms 912 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 912 KB Output is correct
2 Correct 0 ms 912 KB Output is correct
3 Correct 0 ms 912 KB Output is correct
4 Correct 0 ms 912 KB Output is correct
5 Correct 0 ms 912 KB Output is correct
6 Correct 0 ms 912 KB Output is correct
7 Correct 0 ms 912 KB Output is correct
8 Correct 0 ms 912 KB Output is correct
9 Correct 0 ms 912 KB Output is correct
10 Correct 0 ms 912 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 912 KB Output is correct
2 Correct 0 ms 912 KB Output is correct
3 Correct 0 ms 912 KB Output is correct
4 Correct 0 ms 912 KB Output is correct
5 Correct 0 ms 912 KB Output is correct
6 Correct 0 ms 912 KB Output is correct
7 Correct 0 ms 912 KB Output is correct
8 Correct 0 ms 912 KB Output is correct
9 Correct 0 ms 912 KB Output is correct
10 Correct 0 ms 912 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 912 KB Output is correct
2 Correct 0 ms 912 KB Output is correct
3 Correct 0 ms 912 KB Output is correct
4 Correct 0 ms 912 KB Output is correct
5 Correct 0 ms 912 KB Output is correct
6 Correct 0 ms 912 KB Output is correct
7 Correct 0 ms 912 KB Output is correct
8 Correct 0 ms 912 KB Output is correct
9 Correct 0 ms 912 KB Output is correct
10 Correct 0 ms 912 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2568 KB Output is correct
2 Correct 5 ms 1104 KB Output is correct
3 Correct 4 ms 1128 KB Output is correct
4 Correct 23 ms 2280 KB Output is correct
5 Correct 0 ms 912 KB Output is correct
6 Correct 18 ms 2160 KB Output is correct
7 Correct 9 ms 1464 KB Output is correct
8 Correct 40 ms 3192 KB Output is correct
9 Correct 20 ms 2244 KB Output is correct
10 Correct 30 ms 2628 KB Output is correct

Subtask #6
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2568 KB Output is correct
2 Correct 2 ms 1084 KB Output is correct
3 Correct 33 ms 2844 KB Output is correct
4 Correct 7 ms 1320 KB Output is correct
5 Correct 32 ms 2820 KB Output is correct
6 Correct 6 ms 1168 KB Output is correct
7 Correct 23 ms 2472 KB Output is correct
8 Correct 30 ms 2592 KB Output is correct
9 Correct 38 ms 2976 KB Output is correct
10 Correct 25 ms 2376 KB Output is correct