fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. bool isValid(long long val,long long * a,long long n,long long k)
  5. {
  6. 	long long sum=0;
  7. 	long long count1=0;
  8. 	for(long long i=0;i<n;i++)
  9. 	{
  10. 		if(sum+a[i] <= val)
  11. 		{
  12. 			sum+=a[i];
  13. 		}
  14. 		else
  15. 		{
  16. 			count1++;
  17. 			sum=a[i];
  18. 		}
  19. 		//cout<<sum<<endl;
  20. 	}
  21. 	return (count1+1) <= k;
  22. }
  23.  
  24. int main() {
  25.  
  26. 	long long n,k;
  27. 	cin>>n>>k;
  28.  
  29. 	long long a[n];
  30. 	long long maxi=0;
  31. 	for(long long i=0;i<n;i++)
  32. 	{
  33. 		cin>>a[i];
  34. 		if(maxi < a[i])
  35. 		{
  36. 			maxi=a[i];
  37. 		}
  38. 	}
  39.  
  40. 	long long lo = maxi;
  41. 	long long hi = 1e18;
  42. 	int ans;
  43.  
  44. 	//cout<<isValid(7,a,n,k)<<endl;;
  45.  
  46. 	while(lo <= hi)
  47. 	{
  48. 		long long mid = (lo+hi)/2;
  49.  
  50. 		if(isValid(mid,a,n,k))
  51. 		{
  52. 			ans = mid;
  53. 			hi = mid-1;
  54. 		}
  55. 		else
  56. 		{
  57. 			lo =mid+1;
  58. 		}
  59. 	}
  60.  
  61. 	cout<<ans<<endl;
  62.  
  63. 	return 0;
  64. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
5 3
2 4 7 3 5
stdout
copy 
8
https://ideone.com/lsDqKv
language:
C++14 (gcc 8.3)
created:
8 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!