fork(6) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define repn(i,a,n) for(int i=a;i<n;i++)
  4. #define pb push_back
  5. #define TRACE
  6.  
  7. #ifdef TRACE
  8. #define trace1(x)                cerr << #x << ": " << x << endl;
  9. #define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
  10. #define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
  11. #define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
  12. #define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
  13. #define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
  14.  
  15. #else
  16.  
  17. #define trace1(x)
  18. #define trace2(x, y)
  19. #define trace3(x, y, z)
  20. #define trace4(a, b, c, d)    
  21. #define trace5(a, b, c, d, e)
  22. #define trace6(a, b, c, d, e, f)
  23.  
  24. #endif 
  25. int main(){
  26. 	int n;
  27. 	cin>>n;
  28. 	while(n--){
  29. 		int m,k;
  30. 		cin>>m>>k;
  31. 		int a[502];
  32. 		int sum=0;
  33. 		for(int i=1;i<=m;i++){ 
  34. 			cin>>a[i];
  35. 			sum+=a[i];
  36. 		}
  37. 		int lo = *max_element(a+1,a+m+1);
  38. 		int hi = sum;
  39.  
  40. 		while(lo<hi){
  41. 			int mid = lo + (hi-lo)/2;
  42. 			int s=0;
  43. 			int req=1;
  44. 			for(int i=m; i>=1 ; i--){
  45. 				if(s + a[i] <= mid){
  46. 					s += a[i];
  47. 				}
  48. 				else{
  49. 					s = a[i];
  50. 					++req;
  51. 				}
  52. 			}
  53.  
  54. 			if(req<=k)
  55. 				hi = mid;
  56. 			else
  57. 				lo = mid+1;
  58. 		}
  59.  
  60.  
  61. 		vector<int>v;
  62. 		int placed = 1;
  63. 		int s = 0;
  64. 		for(int i=m; i>=1 ; i--){
  65. 			if(s + a[i] <= lo and i-1>(k-1-placed)){
  66. 				s += a[i];
  67. 			}
  68. 			else{
  69. 				s = a[i];
  70. 				placed++;
  71. 				v.push_back(i);
  72. 			}
  73. 		}
  74.  
  75. 		cout<<lo<<"   ";
  76. 		for(int i=0 ; i < v.size() ; i++)
  77. 			cout<<v[i]<<" ";
  78.  
  79. 		// print output here
  80. 	}
  81. }
  82.  
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
1
5 4
1 1 1 1 1
stdout
copy 
2   3 2 1
https://ideone.com/q4PJZg
language:
C++ (gcc 8.3)
created:
7 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!