fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef pair<int,int> pii;
  5. typedef pair<int,pii> pr;
  6. int dp[1005][1005];
  7. int minVal(int n,int wt,vector<int> &arr){
  8. 	if(wt<0){
  9. 		return 1e9;
  10. 	}
  11. 	if(n == 0){
  12. 		if(wt == 0){
  13. 			return 0;
  14. 		}
  15. 		return 1e9;
  16. 	}
  17. 	if(dp[n][wt]!=-1){
  18. 		return dp[n][wt];
  19. 	}
  20. 	if(arr[n-1] == -1){
  21. 		return dp[n][wt] = minVal(n-1,wt,arr);
  22. 	}
  23. 	return dp[n][wt] = min(arr[n-1] + minVal(n,wt-n,arr),minVal(n-1,wt,arr));
  24. }
  25. int main(int argc,char const* argv[]){
  26. 	ios_base::sync_with_stdio(false);
  27. 	cin.tie(nullptr);
  28. 	int n,w;
  29. 	cin>>n>>w;
  30. 	vector<int> arr(n);
  31. 	for(int i=0;i<n;i++){
  32. 		cin>>arr[i];
  33. 	}
  34. 	memset(dp,-1,sizeof(dp));
  35. 	int val = minVal(n,w,arr);
  36. 	if(val > 1e7){
  37. 		cout<<-1<<endl;
  38. 	}else{
  39. 		cout<<val<<endl;
  40. 	}
  41. 	return 0;
  42. }
Success #stdin #stdout 0s 7456KB
comments (?)
stdin 
5 5
1 2 3 4 5
stdout 
5
https://ideone.com/7rz4Kh
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!