fork download
copy 
  1. /// no time to waste
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define ll long long
  5. #define eb emplace_back
  6. #define pii pair <int, int>
  7. #define fi first
  8. #define se second
  9. #define all(ac) ac.begin(), ac.end()
  10. #define MASK(x) (1LL << x)
  11. #define ub(i, j) ((i >> j) & 1)
  12. #define FLIP(x, y) ((MASK(x) - 1) ^ y)
  13.  
  14. const short MX = 10001;
  15. short w[MX], v[MX];
  16. int dp[101][1001];
  17. vector <short> tr;
  18.  
  19. void solve() {
  20.     short n, m; cin >> n >> m;
  21.     for(short i=1;i<=n;i++) cin >> w[i];
  22.  
  23.     for(short i=1;i<=n;i++) cin >> v[i];
  24.  
  25.     short sq = sqrt(n);
  26.     int dp_cur[m + 1];
  27.     memset(dp_cur, 0, sizeof dp_cur);
  28.     for(short i=1;i<=n;i++) {
  29.         for(short j = m;j >= w[i];j--) {
  30.             dp_cur[j] = max(dp_cur[j], dp_cur[j - w[i]] + v[i]);
  31.         }
  32.  
  33.         for(short j = 2;j <= m;j++) if(dp_cur[j] < dp_cur[j - 1]) {
  34.             dp_cur[j] = dp_cur[j - 1];
  35.         }
  36.  
  37.         if(i % sq == 0) {
  38.             short id = i / sq;
  39.             for(short j = 1;j<=m;j++) {
  40.                 dp[id][j] = dp_cur[j];
  41.             }
  42.         }
  43.     }
  44.  
  45.     cout << dp_cur[m] << ' ';
  46.     bool choose[sq][m + 1];
  47.     while(n > 0 && m > 0) {
  48.         short pos_start = (n - 1) / sq * sq + 1;
  49.         short end_block = n;
  50.  
  51.         short id = (pos_start - 1) / sq;
  52.  
  53.         for(short i = 1;i<=m;i++) dp_cur[i] = dp[id][i];
  54.         for(short i = pos_start;i <= end_block; i++) {
  55.             for(short j=1;j<=m;j++) choose[i - pos_start][j] = 0;
  56.             for(short j=m;j>=w[i];j--) {
  57.                 int new_val = dp_cur[j - w[i]] + v[i];
  58.                 if(new_val > dp_cur[j]) {
  59.                     dp_cur[j] = new_val;
  60.                     choose[i - pos_start][j] = 1; 
  61.                 }
  62.             }
  63.  
  64.             for(short j=2;j<=m;j++) if(dp_cur[j - 1] > dp_cur[j]) {
  65.                 dp_cur[j] = dp_cur[j - 1];
  66.                 choose[i - pos_start][j] = choose[i - pos_start][j - 1];
  67.             }
  68.         }
  69.  
  70.         for(short i=end_block - pos_start;i >= 0 && m > 0;i--) if(choose[i][m]) {
  71.             tr.eb(i + pos_start);
  72.             m -= w[i + pos_start];
  73.         }
  74.         n = pos_start - 1;
  75.     }
  76.  
  77.     cout << tr.size() << '\n';
  78.     for(short &v : tr) cout << v << ' ';
  79.     tr.clear();
  80.     return;
  81. }
  82.  
  83. int32_t main() {
  84.     ios::sync_with_stdio(false);
  85.     cin.tie(0), cout.tie(0);
  86.     #define task "tet"
  87.     if(fopen(task".inp", "r")) {
  88.         freopen(task".inp", "r", stdin);
  89.         freopen(task".out", "w", stdout);
  90.     }
  91.  
  92.     int testcase; cin >> testcase;
  93.     while(testcase--) solve();
  94.     return 0;
  95. }
  96.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
1
3 4
1 2 3
4 5 6
stdout
copy 
10 2
3 1
https://ideone.com/gHdJVR
language:
C++ (gcc 8.3)
created:
2 days 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!