fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std ;
  3.  
  4. #define int long long
  5.  
  6. const int M = 105 , X = 1e3 + 5;
  7.  
  8. int dp[M][X] ; 
  9.  
  10. // dp[i][j] tells maximum possible weight we can get from color i to m 
  11. // if we already have j weight with us, provided max ans satisfies weight < x 
  12.  
  13. int solve(vector<int>* v, int m , int x, int i = 1 , int j = 0){
  14. 	if(j > x) return INT_MIN ; // too much weight taken
  15. 	if(i > m) return 0 ; //successfully reached end
  16. 	if(v[i].size() == 0) return INT_MIN ; // no weight of this color present
  17. 	if(dp[i][j] != -1) return dp[i][j] ;
  18. 	int c = INT_MIN ;
  19. 	for(auto k : v[i]){ // k  iterates over all weights of current color v[i]
  20. 		int val = solve(v,m,x,i+1,j+k) ;
  21. 		if(val >= 0) c = max(c,k+val) ;
  22. 	}
  23. 	return dp[i][j] = c ;
  24. }
  25. int32_t main(){
  26. 	int n , m , x ;
  27. 	cin >> n >> m >> x ;
  28. 	vector<int> v[m+1] ; // all colors 1 to m
  29. 	pair<int,int> a[n] ;
  30. 	for(int i = 0 ; i < n ; i++){
  31. 		cin >> a[i].first ; //weight
  32. 	}
  33. 	for(int i = 0 ; i < n ; i++) {
  34. 		cin >> a[i].second ; // color
  35. 	}
  36. 	for(int i = 0 ; i <= m ; i++){
  37. 		for(int j = 0 ; j <= x ; j++) dp[i][j] = -1 ;
  38. 	}
  39. 	for(int i = 0 ; i < n ; i++){ 
  40. 		v[a[i].second].push_back(a[i].first) ;
  41. 	}
  42. 	//paired by color
  43. 	int ans = solve(v,m,x) ;
  44. 	if(ans < 0) cout << -1 ;
  45. 	else cout << x-ans ;
  46. 	return 0 ;
  47. }
  48.  
Success #stdin #stdout 0s 4560KB
comments (?)
stdin
copy 
9 3 10
1 3 5 1 3 5 1 3 5
1 1 1 2 2 2 3 3 3
stdout
copy 
1
https://ideone.com/JshzM5
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!