fork download
copy 
  1. /*
  2.  ####  ####  ####
  3.  ## ##  ##  ## ##
  4.  ##  ## ## ##  ##
  5.  ##   ######   ##
  6.  ##     ## ######
  7.  ###   ####   ###
  8. */
  9. #define _CRT_SECURE_NO_WARNINGS
  10. #include<bits/stdc++.h>
  11. #include<unordered_map>
  12. #define MOD 1000000007
  13. #define pi acos(-1)
  14. #define ull unsigned long long
  15. using namespace std;
  16. long long Mod(long long num, long long mod) { return ((num % mod) + mod) % mod; }
  17. long long Ceil(long long num, long long div) { return (num + div - 1) / div; }
  18. long long Gcd(long long a, long long b) { if (a == 0)return b; return Gcd(b % a, a); }
  19. long long Lcm(long long a, long long b) { return a / Gcd(a, b) * b; }
  20. void fast()
  21. {
  22.     std::ios_base::sync_with_stdio(0);
  23.     cin.tie(0);
  24.     cout.tie(0);
  25. #ifndef ONLINE_JUDGE
  26.     freopen("in.txt", "r", stdin);
  27.     freopen("out.txt", "w", stdout);
  28. #endif
  29. }
  30. vector<vector<int>>Dp1, Dp2;
  31. vector<vector<int>>vis1, vis2;
  32. vector<int>v;
  33. int t, n, id;
  34. int minirem(int i, int rem) {
  35.     if (i >= n)
  36.         return rem;
  37.     int& ret = Dp1[i][rem];
  38.     if (vis1[i][rem] == id)
  39.         return ret;
  40.     vis1[i][rem] = id;
  41.     ret = minirem(i + 1, rem);
  42.     if (v[i] <= rem)
  43.     ret = min(ret, minirem(i + 1, rem - v[i]));
  44.     return ret;
  45. }
  46. int maxinum(int i, int rem) {
  47.     if (i >= n)
  48.         return (rem == 0 ? 0 : -1e9);
  49.     int& ret = Dp2[i][rem];
  50.     if (vis2[i][rem] == id)
  51.         return ret;
  52.     vis2[i][rem] = id;
  53.     ret = maxinum(i + 1, rem);
  54.     if (v[i] <= rem)
  55.         ret = max(maxinum(i + 1, rem - v[i]) + 1,ret);
  56.     return ret;
  57. }
  58. void build(int i, int rem) {
  59.     if (i >= n)
  60.         return;
  61.     if (maxinum(i + 1, rem) == maxinum(i, rem)) {
  62.         build(i + 1, rem);
  63.     }
  64.     else {
  65.         cout << v[i] << " ";
  66.         build(i + 1, rem - v[i]);
  67.     }
  68. }
  69. int main() {
  70.     fast();
  71.     //freopen("cases.in ", "r", stdin);
  72.     id = 0;
  73.     while (1) {
  74.         ++id;
  75.         cin >> t;
  76.         if (t == 0)
  77.             break;
  78.         cin >> n;
  79.         v = vector<int>(n);
  80.         for (auto& it : v)
  81.             cin >> it;
  82.         Dp1 = Dp2 = vector<vector<int>>(n + 2, vector<int>(t + 100));
  83.         vis1 = vis2 = vector<vector<int>>(n + 2, vector<int>(t + 100));
  84.         int mini = minirem(0, t);
  85.         int num=maxinum(0, t - mini);
  86.         cout << num << "\n";
  87.         build(0, t);
  88.         cout << t - mini << "\n";
  89.     }
  90.     return 0;
  91. }
  92.  
Success #stdin #stdout 0.01s 5408KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/IpK9KF
language:
C++14 (gcc 8.3)
created:
1 year 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!