Submission #8409

#	Time	Username	Problem	Language	Result	Execution time	Memory
8409		cki86201	Uniting (kriii2_U)	C++98	0 / 4	0 ms	40268 KiB

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 / 4