Advertisement
willy108

tle knapsack

Nov 24th, 2022
620
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.94 KB | None | 0 0
  1. //misaka and elaina will carry me to red
  2.  
  3. #pragma GCC optimize("O3,unroll-loops")
  4. #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  5.  
  6. #include <iostream>
  7. #include <cmath>
  8. #include <utility>
  9. #include <cassert>
  10. #include <algorithm>
  11. #include <vector>
  12. #include <array>
  13. #include <cstdio>
  14. #include <cstring>
  15. #include <functional>
  16. #include <numeric>
  17. #include <set>
  18. #include <queue>
  19. #include <map>
  20. #include <chrono>
  21. #include <random>
  22.  
  23. #define sz(x) ((int)(x.size()))
  24. #define all(x) x.begin(), x.end()
  25. #define pb push_back
  26. #define eb emplace_back
  27. #define kill(x, s) {if(x){ cout << s << "\n"; return ; }}
  28.  
  29. #ifndef LOCAL
  30. #define cerr while(0) cerr
  31. #endif
  32.  
  33. using ll = long long;
  34. using lb = long double;
  35.  
  36. const lb eps = 1e-9;
  37. const ll mod = 1e9 + 7, ll_max = 1e18;
  38. //const ll mod = (1 << (23)) * 119 +1, ll_max = 1e18;
  39. const int MX = 5e3 +10, int_max = 0x3f3f3f3f;
  40.  
  41. struct {
  42.   template<class T>
  43.   operator T() {
  44.     T x; std::cin >> x; return x;
  45.   }
  46. } in;
  47.  
  48. using namespace std;
  49.  
  50. pair<int, int> dp[MX][MX*2];
  51. //smallest j such that first i neg and first j pos can sum to k if needed
  52.  
  53. int arr[MX];
  54. int sign[MX];
  55. int n, m, t;
  56.  
  57. const int zero = 5e3;
  58.  
  59. void solve(){
  60.     n = in, m =in, t = in;
  61.     int greedy = 0;
  62.     for(int i = 1; i<=n; i++){
  63.         arr[i] = in;
  64.         if(greedy + arr[i] <= t){
  65.             greedy += arr[i];
  66.             sign[i] = -1;
  67.         }else{
  68.             sign[i] = 1;
  69.         }
  70.     }
  71.     vector<int> pos, neg;
  72.     for(int i = 1; i<=n; i++){
  73.         if(sign[i] > 0){
  74.             pos.pb(arr[i]);
  75.         }else{
  76.             neg.pb(arr[i]);
  77.         }
  78.     }
  79.     if(greedy == t){
  80.         cout << sz(neg) << "\n";
  81.         for(int x : neg) cout << x << " "; cout << "\n";
  82.         return ;
  83.     }
  84.     if(sz(pos) == 0 || sz(neg) == 0){
  85.         cout << -1 << "\n";
  86.         return ;
  87.     }
  88.    
  89.     for(int i = 0; i<=sz(neg); i++){
  90.         for(int k = -m; k<=m; k++){
  91.             dp[i][k + zero] = {n+1, 0};
  92.         }
  93.     }
  94.     dp[0][greedy - t + zero] = {0, 0};
  95.     for(int j = 0; j<sz(pos); j++){
  96.         for(int k = -m; k<=m; k++){
  97.             if(j < sz(pos) && k + pos[j] <= m && dp[0][k + zero].first <= j){
  98.                 dp[0][k + pos[j] + zero] = min(dp[0][k + pos[j]+ zero], {j+1, j+1});
  99.             }
  100.         }
  101.     }
  102.     for(int i = 0; i<sz(neg); i++){
  103.         for(int k = -m; k<=m; k++){
  104.             dp[i+1][k + zero] = min(pair(dp[i][k + zero].first, 0), (k + neg[i] <= m ? pair(dp[i][k + neg[i] + zero].first, -(i+1)) : pair((n+1), 0)));
  105.         }
  106.         for(int k = -m; k<=m; k++){
  107.             for(int j = dp[i+1][k + zero].first; j<=dp[i][k + zero].first; j++){
  108.                 if(j < sz(pos) && k + pos[j] <= m && dp[i+1][k + zero].first <= j){
  109.                     dp[i+1][k + pos[j] + zero] = min(dp[i+1][k + pos[j] + zero], {j+1, j+1});
  110.                 }
  111.             }
  112.         }
  113.     }
  114.     int wo = 0;
  115.     for(int i = 0; i<=sz(neg); i++){
  116.         if(dp[i][zero].first <= n){
  117.             wo = i+1;
  118.         }
  119.     }
  120.     cerr << wo << "\n";
  121.     kill(wo == 0, "-1");
  122.     int i = wo-1, k = 0;
  123.     vector<int> res = neg, rem;
  124.     cerr << wo << " " << k << "\n";
  125.     while(i != 0 || k != greedy - t){
  126.         cerr << i << " " << k << "\n";
  127.         int v = dp[i][k + zero].second;
  128.         if(v > 0){
  129.             res.pb(pos[v-1]);
  130.             k -= pos[v-1];
  131.         }else if(v < 0){
  132.             v = -v;
  133.             rem.pb(neg[v-1]);
  134.             k += neg[v-1];
  135.             i--;
  136.         }else{
  137.             i--;
  138.         }
  139.     }
  140.     vector<int> oup(sz(res));
  141.     sort(all(res)); sort(all(rem));
  142.     auto it = set_symmetric_difference(all(res), all(rem), oup.begin());
  143.     oup.resize(it - oup.begin());
  144.     cout << sz(oup) << "\n";
  145.     for(int x : oup) cout << x << " "; cout << "\n";    
  146. }
  147.  
  148. signed main(){
  149.   cin.tie(0) -> sync_with_stdio(0);
  150.  
  151.   int T = 1;
  152.   //cin >> T;
  153.   for(int i = 1; i<=T; i++){
  154.         //cout << "Case #" << i << ": ";
  155.         solve();
  156.     }
  157.   return 0;
  158. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement