Submission #8409

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
8409	2014-09-13T17:13:28 Z	cki86201	Uniting (kriii2_U)	C++	0 / 4	0 ms	40268 KB

U

#include<stdio.h>
#include<queue>
using namespace std;

#define ll long long
#define MOD 1000000007
int a[10000001];
ll ans[2];
priority_queue <int> pq;

int main()
{
//	freopen("input.txt","r",stdin);
	int n;scanf("%d",&n);
	int i;
	for(i=0;i<n;i++){
		int x;scanf("%d",&x);a[x]++;pq.push(-x);
	}
	for(i=1;i<n;i++){
		int t1 = -pq.top();pq.pop();
		int t2 = -pq.top();pq.pop();
		if(t1 != t2)ans[1] += (ll)a[t1]*a[t2]*2;
		else ans[1] += (ll)a[t1]*(a[t1]-1);
		ans[1] %= MOD;
		a[t1]--, a[t2]--, a[t1+t2]++;
		pq.push(-t1-t2);
		ans[0] += t1*t2;
	}
	printf("%lld\n%lld",ans[0],ans[1]);
	return 0;
}

Subtask #1

0.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	0 ms	40268 KB	Output is partially correct
2	Partially correct	0 ms	40268 KB	Output is partially correct
3	Partially correct	0 ms	40268 KB	Output is partially correct
4	Partially correct	0 ms	40268 KB	Output is partially correct
5	Partially correct	0 ms	40268 KB	Output is partially correct
6	Partially correct	0 ms	40268 KB	Output is partially correct
7	Incorrect	0 ms	40268 KB	Output isn't correct
8	Halted	0 ms	0 KB	-