fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include<stdlib.h>
  3. using namespace std;
  4.  
  5. const int MAXN=1000001;
  6. int cnt[MAXN]={};
  7. queue<long> orgQ, addQ;
  8. inline long LeastNumber(long rem=0){
  9.   if(orgQ.empty() or addQ.empty()==0 and addQ.front()<orgQ.front())
  10.     rem=addQ.front(), addQ.pop();
  11.   else
  12.     rem=orgQ.front(), orgQ.pop();
  13.   return rem;
  14. }
  15.  
  16. char buf[1 << 23];
  17.  
  18. int main(){
  19.  
  20.   int N, x;
  21.  
  22.   while(scanf("%d\n",&N) != EOF and N){
  23.     // init
  24.     memset(cnt,0,sizeof(cnt));
  25.     while(orgQ.empty()==0) orgQ.pop();
  26.     while(addQ.empty()==0) addQ.pop();
  27.  
  28.     // CountSort
  29.  
  30.     x = 0;
  31.     for(char *p = fgets(buf,sizeof(buf),stdin); *p != '\n'; ++p){
  32.        if(*p == ' '){
  33.           cnt[x]++;
  34.           x = 0;
  35.           continue;
  36.        }
  37.        x = 10 * x + *p - '0';
  38.     }
  39.     cnt[x]++;
  40.  
  41.    for(int i=1;i<MAXN;i++)
  42.       for(int j=0;j<cnt[i];j++)
  43.         orgQ.push(i);
  44.     long sum=0, min_one, min_two;
  45.     for(int t=1; t<N; t++){
  46.       min_one=LeastNumber(),
  47.       min_two=LeastNumber(),
  48.       sum+=min_one+min_two;
  49.       addQ.push(min_one+min_two);
  50.     }
  51.     printf("%ld\n",sum);
  52.   }
  53. }
Success #stdin #stdout 0s 27336KB
comments (?)
stdin
copy 
3
1 2 3
4
1 2 3 4
0
stdout
copy 
9
19
https://ideone.com/usX8gE
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!