Submission #9786

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
9786	2014-09-28T08:55:50 Z	silas	Uniting (kriii2_U)	C++	0 / 4	20 ms	1676 KB

U

#include <iostream>
#include <queue>
#include <functional>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	priority_queue<int, vector<int>, greater<int> > min_heap;
	vector<int> arr;
	int cost = 0; // 비용의 합의 최솟값
	int num, temp; // num : 부서의 수
	cin >> num;
	for (int i = 0 ; i < num; i++) {
		cin >> temp;
		arr.push_back(temp);
		min_heap.push(temp);
	}
	sort(arr.begin(), arr.end());
	while (arr.size() > 1) {
		cost += arr[0] * arr[arr.size() - 1];
		int tmp = arr[0] + arr[arr.size() - 1];
		arr.erase(arr.begin()); arr.pop_back();
		arr.push_back(tmp);
		sort(arr.begin(), arr.end());
	}
	int cost2 = 0;
	while (min_heap.size() > 1) {
		int tmp1 = min_heap.top(); min_heap.pop();
		int tmp2 = min_heap.top(); min_heap.pop();
		cost2 += tmp1 * tmp2;
		min_heap.push(tmp1 + tmp2);
	}
	cost < cost2 ? cout << cost << endl : cout << cost2 << endl;
	
	return 0;
}

Subtask #1

0.0 / 4.0

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