fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {
  5.  
  6.   int t;
  7.   cin>>t;
  8.   while(t--)
  9.   {
  10.     int n;
  11.     cin>>n;
  12.     vector<int> a(n);
  13.     vector<int> odds;
  14.     vector<int> evens;
  15.     for(int i=0; i<n; i++)
  16.     {
  17.       cin>>a[i];
  18.       if(a[i]%2==0) evens.push_back(a[i]);
  19.       else odds.push_back(a[i]);
  20.     }
  21.  
  22.     sort(evens.begin(),evens.end(),greater<int>());
  23.     sort(odds.begin(),odds.end(),greater<int>());
  24.  
  25.     int num_even = evens.size();
  26.     vector<long long> pf(num_even+1,0);
  27.     for(int i=0;i<num_even;i++)
  28.     {
  29.       pf[i+1]=pf[i]+evens[i];
  30.     }
  31.  
  32.  
  33.  
  34.     for(int k=1; k<=n; k++)
  35.     { 
  36.  
  37.       int even_used = min(k-1,num_even);
  38.       int waste_odds_needed = (k-1)-even_used;
  39.  
  40.       if(odds.size()==0)
  41.       {
  42.         cout<<"0 ";
  43.         continue;
  44.       }
  45.       long long sum;
  46.  
  47.       if(even_used==(k-1))
  48.       {
  49.         sum = odds[0] + pf[even_used];
  50.         cout<<sum<<" ";
  51.       }
  52.       else
  53.       {
  54.         if(waste_odds_needed%2==0)
  55.         {
  56.           sum = odds[0] + pf[even_used];
  57.           cout<<sum<<" ";
  58.         }
  59.         else
  60.         {
  61.           if(even_used>0 && (odds.size()-1)%2==0)
  62.           {
  63.             sum = odds[0] + pf[even_used-1];
  64.             cout<<sum<<" ";
  65.           }
  66.           else
  67.           {
  68.             cout<<"0 ";
  69.           }
  70.         }
  71.       }
  72.  
  73.  
  74.     }
  75.  
  76.     cout<<endl;
  77.  
  78.  
  79.  
  80.  
  81.  
  82.  
  83.   }
  84.  
  85.  
  86.  
  87.  
  88.  
  89.  
  90. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
6

3

1 1 1

3

1 2 3

5

4 1 3 1 2

5

4 2 3 1 3

3

4 1 2

3

4 2 2
stdout
copy 
1 0 1 
3 5 0 
3 7 9 7 9 
3 7 9 7 9 
1 5 7 
0 0 0
https://ideone.com/3S5uv7
language:
C++ (gcc 8.3)
created:
2 days 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!