fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #ifdef LOCAL
  5. #include "debug2.h"
  6. #else
  7. #define debug(...) 42
  8. #endif
  9.  
  10. #define int long long
  11. #define all(x) (x).begin(), (x).end()
  12. #define rall(x) (x).rbegin(), (x).rend()
  13.  
  14. template<typename T> bool ckmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
  15. template<typename T> bool ckmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
  16.  
  17. const char el = '\n';
  18. const int N = 1000 + 15;
  19.  
  20. int dp[N][N][2];
  21. int a[N];
  22. int trace[N];
  23.  
  24. void solve() {
  25.     int T;
  26.     cin >> T;
  27.     int n;
  28.     cin >> n;
  29.  
  30.     for (int i = 1; i <= n; ++i) cin >> a[i];
  31.     memset(dp, 0, sizeof(dp));
  32.  
  33.     for (int i = 1; i <= n; ++i)
  34.         for (int j = 0; j <= T; ++j) {
  35.             dp[i][j][0] = dp[i - 1][j][0];
  36.             dp[i][j][1] = dp[i - 1][j][1];
  37.  
  38.             if (j - a[i] >= 0) {
  39.                 if (ckmax(dp[i][j][0], dp[i - 1][j - a[i]][0] + 1)) {
  40.                     dp[i][j][1] = dp[i - 1][j - a[i]][1] + a[i];
  41.                     trace[j] = i;
  42.                 } else {
  43.                     if (dp[i][j][0] == dp[i - 1][j - a[i]][0] + 1) {
  44.                         if (ckmax(dp[i][j][1], dp[i - 1][j - a[i]][1] + a[i])) {
  45.                             trace[j] = i;
  46.                         } else {
  47.                             if (dp[i][j][1] == dp[i - 1][j - a[i]][1] + a[i]) {
  48.                                 if (trace[j - a[i]] > trace[j]) {
  49.                                     trace[j] = i;
  50.                                 }
  51.                             }
  52.                         }
  53.                     }
  54.                 }
  55.             }
  56.         }
  57.  
  58.     int ans = dp[n][T][0];
  59.     vector<int> used(n + 5, false);
  60.     {
  61.         for (int i = dp[n][T][1]; i > 0; ) {
  62.             used[trace[i]] = true;
  63.             i -= a[trace[i]];
  64.         }
  65.     }
  66.  
  67.     // for (int i = 1; i <= n; ++i) {
  68.     //     cout << used[i] << ' ';
  69.     // }
  70.     // cout << el;
  71.  
  72.     int m;
  73.     cin >> m;
  74.     vector<int> b(m);
  75.     for (int i = 0; i < m; ++i)
  76.         cin >> b[i];
  77.     for (int i = 1; i <= n; ++i)
  78.         if (!used[i]) b.push_back(a[i]);
  79.     sort(all(b));
  80.     for (int i = 0, sum = 0; i < (int) b.size(); ++i)
  81.     {
  82.         sum += b[i];
  83.         if (sum <= T)
  84.         {
  85.             ++ans;
  86.             continue;
  87.         }
  88.         break;
  89.     }
  90.     cout << ans << '\n';
  91. }
  92.  
  93. signed main() {
  94.     ios::sync_with_stdio(false); cin.tie(nullptr);
  95.  
  96.     int testcase = 1;
  97. //    cin >> testcase;
  98.     while (testcase--) {
  99.         solve();
  100.     }
  101.  
  102.     return 0;
  103. }
  104.  
  105.  
  106.  
Success #stdin #stdout 0.01s 19696KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/n6FWgT
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!