fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include<algorithm>
  3. #include<unordered_set>
  4. #include<unordered_map>
  5. using namespace std;
  6. using namespace std::chrono;
  7. #define pii pair<int,pair<int,int>>
  8. #define pi pair<int,int>
  9. #define MAXSIZE 100
  10. #define ll long long
  11. const int MOD = 1e9 + 7;
  12. const int MAXBIT = 30;
  13. const int INF = INT_MAX;
  14. const int NINF= INT_MIN;
  15.  
  16. void printArr(string str, vector<int> arr){
  17. 	cout<<str<<endl;
  18. 	for(int val: arr)
  19. 		cout<<val<<" ";
  20. 	cout<<endl;
  21. }
  22.  
  23.  
  24.  
  25. /*----START CODING FROM HERE-------*/
  26.  
  27. int dfs(int idx, vector<int> &sum, vector<int> &A, int k, int maxBucketSize){
  28. 	int n= A.size();
  29. 	if(idx == n){
  30. 		return 1;
  31. 	}
  32.  
  33. 	//try placing in one of the kth buckets
  34. 	for(int i=0;i<k;i++){
  35. 		if(sum[i] + A[idx] > maxBucketSize) continue;
  36.  
  37. 		sum[i]+= A[idx];
  38. 		int res= dfs(idx+1, sum, A, k, maxBucketSize);
  39. 		sum[i]-= A[idx];
  40.  
  41. 		if(res == 1) return 1;// subset possible with this maxbucketSize
  42. 	}
  43.  
  44. 	return 0;
  45. };
  46.  
  47. int solve(vector<int> A, int k){
  48. 	int n=A.size();
  49. 	vector<int> sum1(k,0);
  50.  
  51. 	int l= *min_element(A.begin(), A.end());
  52. 	int r= accumulate(A.begin(),A.end(),0);
  53. 	int ans=-1;
  54.  
  55. 	while(l<=r){
  56. 		int mid= l+(r-l)/2;
  57. 		vector<int> sum(k,0);
  58.  
  59. 		if(dfs(0,sum,A,k,mid) == 1){
  60. 			ans=mid;
  61. 			r=mid-1;
  62. 		}else{
  63. 			l=mid+1;
  64. 		}
  65. 	}
  66.  
  67. 	return ans;
  68. }
  69.  
  70.  
  71. int main() {
  72.     vector<int> A{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  73.     int k=6;
  74.  
  75.     auto start = high_resolution_clock::now();
  76.     cout<<solve(A,k)<<endl;
  77.     auto stop = high_resolution_clock::now();
  78.  
  79. 	auto duration = duration_cast<milliseconds>(stop - start);
  80.   	cout<<"Time(ms): "<<duration.count();
  81.  
  82.   	return 0;
  83. }
Success #stdin #stdout 0.01s 5412KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
10
Time(ms): 4
https://ideone.com/nyza48
language:
C++14 (gcc 8.3)
created:
2 years 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!