fork download 
  1. #include <bits/stdc++.h> 
  2. using namespace std;
  3. #define all(ac) ac.begin(), ac.end()
  4. #define fi first
  5. #define se second
  6. #define pii pair <int, int>
  7. #define task "exchange"
  8. #define db double
  9. #define pb push_back
  10. #define eb emplace_back
  11. #define bit(x, y) ((x >> y) & 1)
  12.  
  13. void pre_calc(vector <pii> &vt, int v, int cnt, int w = 1) {
  14.     while(w <= cnt) {
  15.         cnt -= w;
  16.         vt.pb(make_pair(v, w));
  17.         w <<= 1;
  18.     }
  19.     if(cnt > 0) vt.pb(make_pair(v, cnt));
  20.     return;
  21. }
  22.  
  23. int32_t main() {
  24.     ios::sync_with_stdio(false);
  25.     cin.tie(0), cout.tie(0);
  26.     if(fopen(task".inp", "r")) {
  27.         freopen(task".inp", "r", stdin);
  28.         freopen(task".out", "w", stdout);
  29.     }
  30.     int n, P; cin >> n >> P;
  31.     int lim = P << 1 | 1;
  32.     vector <int> rv, cnt(lim + 1, 0);
  33.     for(int i=1;i<=n;i++) {
  34.         int x; cin >> x;
  35.         cnt[x]++;
  36.         if(cnt[x] == 1) rv.eb(x);
  37.     }
  38.     sort(all(rv));
  39.     int diff = rv.size();
  40.     vector <pii> vt;
  41.     for(int i : rv) {
  42.         pre_calc(vt, i, cnt[i] - 1);
  43.     }
  44.     int f[lim + 1];
  45.     memset(f, 0, sizeof f);
  46.     f[0] = 1;
  47.     pii pre[lim + 1];
  48.     for(pii val : vt) {
  49.         for(int i=lim;i>=val.se * val.fi;i--) {
  50.             if(f[i] == 0 && f[i - val.se * val.fi] == 1) f[i] = 1, pre[i] = val;
  51.         }
  52.     }
  53.  
  54.     int dp[diff + 1][lim + 1];
  55.     int p[diff + 1][lim + 1];
  56.     for(int i=1;i<=lim;i++) dp[0][i] = n + 5;
  57.     dp[0][0] = 0;
  58.     for(int i=1;i<=diff;i++) {
  59.         for(int j=lim;j>=0;j--) {
  60.             dp[i][j] = dp[i - 1][j];
  61.             p[i][j] = 0;
  62.         }
  63.         for(int j=lim;j>=rv[i - 1];j--) {
  64.             if(dp[i][j] > dp[i][j - rv[i - 1]] + 1) {
  65.                 dp[i][j] = dp[i][j - rv[i - 1]] + 1;
  66.                 p[i][j] = 1;
  67.             }
  68.         }
  69.     }
  70.  
  71.     int rem = n + 3, w = lim + 6;
  72.     int id = -1;
  73.     int pos_j = lim;
  74.     int p1, p2;
  75.     for(int pos_i = 0;pos_i<=lim;pos_i++) {
  76.         while(pos_i + pos_j >= P) {
  77.             if(f[pos_j] == 1) id = pos_j;
  78.             pos_j--;
  79.         }
  80.         if(dp[diff][pos_i] < 1e6 && id != -1) {
  81.             if(rem > dp[diff][pos_i]) {
  82.               rem = dp[diff][pos_i];
  83.               w = pos_i + id;
  84.               p1 = pos_i, p2 = id;
  85.             }
  86.             else
  87.             if(rem == dp[diff][pos_i]) {
  88.                 if(w > pos_i + id) {
  89.                     w = pos_i + id;
  90.                     p1 = pos_i, p2 = id;
  91.                 }
  92.             }
  93.         }
  94.     }
  95.     cout << diff - rem << ' ' << w << '\n';
  96.     vector <int> ans;
  97.     while(p2 > 0) {
  98.         int cnt = pre[p2].se;
  99.         while(cnt--) ans.eb(pre[p2].fi);
  100.         p2 -= pre[p2].fi * pre[p2].se;
  101.     }
  102.     for(int i=diff;i>=1;i--) {
  103.         if(p[i][p1] == 1) ans.eb(rv[i - 1]), p1 -= rv[i - 1];
  104.         if(p1 == 0) break;
  105.     }
  106.     sort(all(ans));
  107.     for(int x : ans) cout << x << ' ';
  108.     return 0;
  109. }
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin 
8 21
5 5 5 0 7 4 7 9
stdout 
4 21
4 5 5 7
https://ideone.com/YYARRw
language:
C++14 (gcc 8.3)
created:
10 hours 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!