Advertisement
Guest User

Untitled

a guest
Mar 2nd, 2015
195
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.04 KB | None | 0 0
  1.  
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. #define LOCAL
  6. #define INPUT 1
  7. #define OUTPUT 0
  8.  
  9. typedef unsigned long long ull;
  10. typedef long long ll;
  11. typedef long double ld;
  12.  
  13. #define forn(i, n) for (int i = 0; i < n; i++)
  14. #define fornn(i, q, n) for (int i = q; i < n; i++)
  15. #define ll long long
  16. #define mp make_pair
  17. #define pb push_back
  18. #define all(v) v.begin(), v.end()
  19. #define times clock() * 1.0 / CLOCKS_PER_SEC
  20.  
  21. #define TASK "gg"
  22.  
  23. using namespace std;
  24.  
  25. const double eps = 1e-7;
  26. const double pi = acos(-1.0);
  27.  
  28. const int INF = 2e9 + 1;
  29. const ll LINF = 8e18;
  30. const ll MM = 1e9 + 7;
  31.  
  32. int solve();
  33.  
  34. int main()
  35. {
  36. #ifdef LOCAL
  37.     if (INPUT)
  38.         //freopen(TASK".in", "r", stdin);
  39.         freopen("input.txt", "r", stdin);
  40.     if (OUTPUT)
  41.         //freopen(TASK".out", "w", stdout);
  42.         freopen("output.txt", "w", stdout);
  43.     ios_base::sync_with_stdio(0);
  44.     cin.tie(0);
  45. #else
  46.     if (INPUT)
  47.         freopen(TASK".in", "r", stdin);
  48.     if (OUTPUT)
  49.         freopen(TASK".out", "w", stdout);
  50.     ios_base::sync_with_stdio(0);
  51.     cin.tie(0);
  52. #endif
  53.  
  54.     solve();
  55.  
  56. #ifdef LOCAL
  57.     cerr.precision(3);
  58.     cerr << "\nTIME: " << times << "\n";
  59. #endif
  60.     return 0;
  61. }
  62.  
  63. ll dp[10007], weights[107], c[107], path[10007];
  64.  
  65. void go(int i)
  66. {
  67.     if (path[i] != -1)
  68.     {
  69.         go(i - weights[path[i]]);
  70.         cout << path[i] + 1 << "\n";
  71.     }
  72. }
  73.  
  74. int solve()
  75. {
  76.     int n,v;
  77.     cin >> v >> n;
  78.     forn(i, v)
  79.         cin >> weights[i];
  80.     forn(i, v)
  81.         cin >> c[i];
  82.     forn(i, n + 1)
  83.     {
  84.         path[i] = -1;
  85.         dp[i] = -1;
  86.     }
  87.     dp[0] = 0;
  88.     forn(i, v)
  89.         for (int w = n; w >= weights[i]; w--)
  90.             if (dp[w - weights[i]] != -1)
  91.             {
  92.                 if (dp[w - weights[i]] + c[i] >= dp[w])
  93.                 {
  94.                     dp[w] = dp[w - weights[i]] + c[i];
  95.                     path[w] = i;
  96.                 }
  97.             }
  98.  
  99.     int ind = n;
  100.     for(int i = n; i >= 0; i--)
  101.         if (dp[i] > dp[ind])
  102.             ind = i;
  103.     go(ind);
  104.     return 0;
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement