fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int no[201],il[201],w,dp[201][20001];
  4.  
  5. int main(){
  6. 	int n;
  7. 	cin>>n;
  8. 	for(int i=1;i<=n;i++) cin>>no[i];
  9. 	for(int i=1;i<=n;i++) cin>>il[i];
  10. 	cin>>w;
  11. 	for(int i=1;i<=n;i++){
  12. 		for(int j=1;j<=w;j++){
  13. 			dp[i][j]=dp[i-1][j];
  14. 			for(int k=1;k<=il[i];k++){
  15. 				if(j-k*no[i]>=0&&dp[i-1][j-k*no[i]]+k>dp[i][j]){
  16. 					if(dp[i-1][j-k*no[i]]==0){
  17. 						if(j%no[i]!=0) continue;
  18. 					}
  19. 					dp[i][j]=dp[i-1][j-k*no[i]]+k;
  20. 				}
  21. 				else if(j-k*no[i]<0) break;
  22. 			}
  23. 			cout<<dp[i][j]<<' ';
  24. 		}cout<<endl;
  25. 	}
  26. 	cout<<dp[n][w];
  27. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
3
2 3 5
2 2 1
10
stdout
copy 
0 1 0 2 0 2 0 2 0 2 
0 1 1 2 2 2 3 3 3 4 
0 1 1 2 2 2 3 3 3 4 
4
https://ideone.com/DI96ia
language:
C++ (gcc 8.3)
created:
12 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!