Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10954 - Add All

Use a priority_queue.
Check input and AC output for thousands of problems on uDebug!

Hasselli
New poster
Posts: 22
Joined: Mon Apr 16, 2012 8:08 pm
Contact:

### Re: 10954 - Add All

brianfry713 wrote:Use a priority_queue.
I don't know what is this?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10954 - Add All

Check input and AC output for thousands of problems on uDebug!

Hasselli
New poster
Posts: 22
Joined: Mon Apr 16, 2012 8:08 pm
Contact:

### Re: 10954 - Add All

Code: Select all

``````#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int main(){
int n;
cin >> n;
while (!n == 0){
priority_queue<int> a;
int b;
int cost = 0;
int sum = 0;
if (n == 2){
int c;
cin >> b >> c;
cout << b + c;
}
else{
for (int i = 1; i <= n; i++){
cin >> b;
a.push(b);
}
for (int i = 3; i<= n; i++){
sum += cost;
cost += a.top();
a.pop();
}
sum += cost;
cout << sum << endl;
}
cin >> n;
}
}``````
Why wrong?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10954 - Add All

Your algorithm is wrong and the result doesn't match the sample input.

Push the input onto the priority_queue.
Add the sum of the two smallest numbers to the cost, push the sum back on the queue. Repeat until there is only one number left on the queue.
Check input and AC output for thousands of problems on uDebug!

Hasselli
New poster
Posts: 22
Joined: Mon Apr 16, 2012 8:08 pm
Contact:

### Re: 10954 - Add All

Code: Select all

``````#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int main(){
int n;
cin >> n;
while (!n == 0){
priority_queue<int> a;
int b;
int cost = 0;
int sum = 0;
if (n == 2){
int c;
cin >> b >> c;
cout << b + c;
}
else{
for (int i = 1; i <= n; i++){
cin >> b;
a.push(b);
}
while (a.size() > 1){
b = a.top();
a.pop();
a.push(a.top() + b);
a.pop();
}
cout << a.top() << endl;
}
cin >> n;
}
}``````
Do you mean this?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10954 - Add All

No. That doesn't match the sample input. First read the two smallest elements from the priority_queue. Then add the sum to the cost and place the sum back on the priority_queue. Don't output the final sum that should be on the priority_queue, but the cost.
Check input and AC output for thousands of problems on uDebug!

Hasselli
New poster
Posts: 22
Joined: Mon Apr 16, 2012 8:08 pm
Contact:

### Re: 10954 - Add All

How to find two smallest?

Hasselli
New poster
Posts: 22
Joined: Mon Apr 16, 2012 8:08 pm
Contact:

### Re: 10954 - Add All

error C2064: term does not evaluate to a function taking 2 arguments xutility

I got this error with this code:

Code: Select all

``removed after AC``
Last edited by Hasselli on Sat May 05, 2012 5:44 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10954 - Add All

priority_queue< int, vector<int>, greater<int> > a;
Check input and AC output for thousands of problems on uDebug!

Hasselli
New poster
Posts: 22
Joined: Mon Apr 16, 2012 8:08 pm
Contact:

### Re: 10954 - Add All

Thank you very much Brian.

sumon sarker
New poster
Posts: 4
Joined: Tue Mar 20, 2012 7:58 am
Contact:

### Re: 10954 - Add All

I am getting wrong answer! Please give me some other sample input/output.........

shuvrothpol1
New poster
Posts: 17
Joined: Wed Aug 15, 2012 12:37 pm

### Re: 10954 - Add All

6
9 9 9 9 9 9
how can it possible that the answer is 144 ? The answer should be 180. Shouldn't it ? If I am wrong please inform me where is my mistake.Because, i got WA of it.Besides, I use bubble sort to solve the problem ..

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10954 - Add All

9,9,9,9,9,9
9+9=18, total cost=18
9,9,9,9,18
9+9=18, total cost=36
9,9,18,18
9+9=18, total cost=54
18,18,18
18+18=36, total cost=90
18,36
18+36=54, total cost=144
Check input and AC output for thousands of problems on uDebug!

CyberPunk
New poster
Posts: 7
Joined: Sat Mar 02, 2013 11:11 pm

### Re: 10954 - Add All

Code: Select all

``````#include <stdio.h>
#include <string.h>
void sort(long long int array[], long long int length)
{
long long int i,j,count,pos,min[10000][2];

for(i=0;i<length;i++) {
min[i][1]=0;
}
for(i=0;i<length;i++) {
count=0;
for(j=0;j<length;j++) {
if(array[i]<array[j]) count++;
}
pos=++min[count][1];
min[count+pos-1][0]=array[i];
}
for(i=0;i<length;i++) array[i]=min[i][0];
}

int main()
{
long long int num[10000],N,i,j,k,l,sum,temp;
while(scanf("%lld",&N)==1 && N) {
i=0;
for(i=0;i<N;i++) scanf("%lld",&num[i]);
sort(num,N);
sum=0,temp=0;
if(N==1) printf("%lld\n",num[0]);
else {
for(i=N-1;i-1>=0;i--) {
temp=num[i-1]+num[i];
sum+=temp;
num[i-1]=temp;
num[i]=0;
sort(num,N);
}

printf("%lld\n",sum);
}
memset(num,0,sizeof(num));
}
return 0;
}
``````
why do i get TLE? any suggestions?