fork download
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. int main(){
  6. int n; cin>>n;
  7. vector<int>w(n),v(n);
  8. for(int i=0;i<n;i++)cin>>w[i];
  9. for(int i=0;i<n;i++)cin>>v[i];
  10. int cap; cin>>cap;
  11. vector<vector<int>>dp(n+1,vector<int>(cap+1));
  12. for(int i=1;i<=n;i++)
  13. for(int j=1;j<=cap;j++)
  14. dp[i][j]=w[i-1]<=j?max(v[i-1]+dp[i-1][j-w[i-1]],dp[i-1][j]):dp[i-1][j];
  15. int h=dp[n][cap];
  16. cout<<h/10<<" "<<h%10;
  17. }
  18.  
Success #stdin #stdout 0.01s 5312KB
stdin
5
5 4 7 8 10
10 5 7 12 8
20
stdout
2 9