volletry

Untitled

Nov 28th, 2021 (edited)
672
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. const int inf = 1e9;
  5. int main() {
  6.     fast_io;
  7.    
  8.     int n, m;
  9.     cin >> m >> n;
  10.  
  11.     vector<int> dp(m + 1, inf);
  12.     vector<int> pred(m + 1);
  13.  
  14.     for (int i = 0; i < n; i++) {
  15.         int t;
  16.         cin >> t;
  17.         for (int j = t + 1; j <= m; j++) {
  18.             if (dp[j] > dp[j - t] + 1)
  19.                 dp[j] = dp[j - t] + 1, pred[j] = j - t;
  20.         }
  21.         dp[t] = 1;
  22.         pred[t] = 0;
  23.     }
  24.  
  25.     cout << dp[m] << '\n';
  26.     vector<int> ans;
  27.     int cur = m;
  28.     while (cur != 0) {
  29.         ans.push_back(cur - pred[cur]);
  30.         cur = pred[cur];
  31.     }
  32.     for (auto i : ans)
  33.         cout << i << ' ';
  34.     return 0;
  35. }
RAW Paste Data