Moderator: Board moderators

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

### Re: 10954 - Add All

To get the minimum total cost, you should always add the two smallest numbers. You can accomplish that using a priority queue.

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!

bgcsaif
New poster
Posts: 38
Joined: Mon Sep 29, 2014 4:03 pm

### Re: 10954 - Add All

What should be output of single input

Code: Select all

``````1
87
0
``````
And should I print new line after each case output?

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10954 - Add All

There won't be input where N = 1. According to problem description N >= 2.
Each test case will start with a positive number, N (2 ? N ? 5000)
Sort array. Each time get sum of two smallest numbers then place new sum into array to preserve it sorted and add current sum to total cost. A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

bgcsaif
New poster
Posts: 38
Joined: Mon Sep 29, 2014 4:03 pm

### Re: 10954 - Add All

Thank you very much to get me out of my confusion. Sometimes over thinking makes one to think so complex that he forgets the simplest thing. I got Accepted! Thanks lighted

tanvir cse
New poster
Posts: 2
Joined: Wed Oct 22, 2014 11:20 am

### 10954

why it time limit?????

Code: Select all

``````/*      TANVIR HASAN */

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <string>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <algorithm>
#include <iterator>
#include <bitset>

//#include <bits/stdc++.h>
using namespace std;

#define uu         first
#define vv         second
#define pb         push_back
#define mp         make_pair
#define LL         long long
#define inf        INT_MAX/3
#define mod        1000000007ll
#define PI         acos(-1.0)
#define linf       (1ll<<60)-1
#define FOR(I,A,B)  for(int I = (A); I < (B); ++I)
#define ALL(A)     ((A).begin(), (A).end())
#define set0(ar)   memset(ar,0,sizeof ar)
#define setinf(ar) memset(ar,126,sizeof ar)
#define vsort(v)   sort(v.begin(),v.end())
#define pii        pair<int,int>

template <class T> inline T bigmod(T p,T e,T M)
{
LL ret = 1;
for(; e > 0; e >>= 1)
{
if(e & 1) ret = (ret * p) % M;
p = (p * p) % M;
}
return (T)ret;
}
template <class T> inline T gcd(T a,T b)
{
if(b==0)return a;
return gcd(b,a%b);
}
template <class T> inline T modinverse(T a,T M)
{
return bigmod(a,M-2,M);
}

int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);

int n,m,p;
vector<int> cst;
while(scanf("%d",&n)==1 && n)
{

vector<int> cst;
FOR(i,0,n)
{
scanf("%d",&m);
cst.pb(m);
}
m=0;
while(cst.size()!=1)
{

vsort(cst);
p=cst+cst;
cst.pb(p);
m+=p;
cst.erase(cst.begin(),cst.begin()+2);
}
// vsort(cst);
cout<<m<<endl;

}

return 0;
}``````
Last edited by brianfry713 on Fri Jun 19, 2015 6:59 am, edited 1 time in total.