fork download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <string>
  6. #include <vector>
  7. #include <set>
  8. #include <utility>
  9. #include <math.h>
  10. #include <cstdlib>
  11. #include <memory.h>
  12. #include <queue>
  13.  
  14. #define pb push_back
  15. #define i64 long long
  16. #define mp make_pair
  17. #define pii pair <int,int>
  18. #define vi vector <int>
  19. #define vii vector <pii>
  20. #define f first
  21. #define s second
  22. #define foran(i,a,b) for (int i=a;i<(int)b;i++)
  23. #define forn(i,n) for (int i=0;i<(int)n;i++)
  24. #define ford(i,n) for (int i=(int)n-1;i>=0;i--)
  25. #define sqr(x) (x) * (x)
  26.  
  27. const double eps = 1e-9;
  28. const int int_inf = 1 << 31 - 1;
  29. const i64 i64_inf = 1ll << 63 - 1;
  30. const double pi = acos(-1.0);
  31.  
  32. using namespace std;
  33.  
  34. vector < pair <int,i64> > a[2];
  35. int n, m;
  36. int W[20]; int C[20];
  37. int T;
  38.  
  39. i64 res;
  40.  
  41. void build(int l, int r, int to) //a[to][i] -> pair <W, C>
  42. {
  43.  for (int i = l; i <= r; i++)
  44.  {
  45.      int sz = (int)a[to].size();
  46.      forn(j, sz)
  47.       forn(c, i + 2)
  48.        a[to].pb( mp(a[to][j].f + (i64)c * W[i], a[to][j].s + (i64)c * C[i]) );
  49.      forn(c, i + 2)
  50.       a[to].pb( mp((i64)c * W[i], (i64)c * C[i]) );
  51.  }
  52.  sort(a[to].begin(), a[to].end());
  53. }
  54.  
  55. i64 solve()
  56. {
  57.      a[0].clear(); a[1].clear();
  58.      build(0, min(9, n - 1), 0);
  59.  
  60.      if  (n <= 10)
  61.      {
  62.          forn(i, a[0].size())
  63.           if  (a[0][i].f <= m) res = max(res, a[0][i].s); else break;
  64.          return res;
  65.      }
  66.  
  67.      build(10, n - 1, 1);
  68.  
  69.      i64 ma = 0;
  70.      forn(i, a[1].size())
  71.       ma = max(a[1][i].s, ma), a[1][i].s = ma;
  72.  
  73.      int r = (int)a[1].size() - 1;
  74.  
  75.      forn(i, a[0].size())
  76.      {
  77.         while (r >= 0 && a[1][r].f + a[0][i].f > m) r--;
  78.         if  (a[1][r].f + a[0][i].f > m) break;
  79.         res = max(res, a[1][r].s + a[0][i].s);
  80.      }
  81.      return res;
  82. }
  83.  
  84. int main() {
  85.   cin >> T;
  86.   forn(TT, T)
  87.   {
  88.       scanf("%d%d", &n, &m);
  89.  
  90.       forn(i, n)
  91.        scanf("%d", &W[i]);
  92.       forn(i, n)
  93.        scanf("%d", &C[i]);
  94.  
  95.       res = 0;
  96.       printf("%I64d\n", solve());
  97.   }
  98.   return 0;
  99. }
  100.  
Success #stdin #stdout 0.01s 2864KB
comments (?)
stdin
copy 
2 
2 4 
3 2 
5 3 
3 100 
4 7 1 
5 9 2
stdout
copy 
                                                               6
                                                              29
https://ideone.com/1u90Q
language:
C++ (gcc 8.3)
created:
12 years 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!