fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef unsigned long long ull;
  7. typedef pair<int, int> pii;
  8. typedef pair<ll, ll> pll;
  9. typedef vector<int> vi;
  10. typedef vector<ll> vll;
  11. typedef string str;
  12.  
  13. #define pb push_back
  14. #define mp make_pair
  15. #define fi first
  16. #define se second
  17. #define all(x) (x).begin(), (x).end()
  18. #define len(x) ((int)(x).size())
  19.  
  20. #define forn(i, n) for (int i = 0; i < (int)(n); ++i)
  21. #define forr(i, l, r) for (int i = (int)(l); i <= (int)(r); ++i)
  22. #define ford(i, r, l) for (int i = (int)(r); i >= (int)(l); --i)
  23.  
  24. #define cmin(a, b) a = min(a, b)
  25. #define cmax(a, b) a = max(a, b)
  26.  
  27. int main() {
  28.     ios_base::sync_with_stdio(false);
  29.     cin.tie(NULL);
  30.  
  31. 	int n, d;
  32. 	cin >> n >> d;
  33.  
  34. 	int w[n + 2];
  35. 	forn(i, n){
  36. 		cin >> w[i];
  37. 	}
  38.  
  39. 	int left = 0, right = 2000000000;
  40. 	while(left < right){
  41. 		int mid = (left + right)/2;
  42.  
  43. 		int s = 0, d_cnt = 0;
  44. 		forn(i, n){
  45. 			s += w[i];
  46. 			if(s > mid){
  47. 				d_cnt++;
  48. 				s = w[i];
  49. 			}
  50. 		}
  51. 		if(s > 0){
  52. 			d_cnt++;
  53. 		}
  54.  
  55. 		if(d_cnt > d){
  56. 			left = mid + 1;
  57. 		}
  58. 		if(d_cnt <= d){
  59. 			right = mid;
  60. 		}
  61. 	}
  62.  
  63. 	cout << left << endl;
  64.  
  65.     return 0;
  66. }
  67.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
5 3
3 2 2 4 1
stdout
copy 
5
https://ideone.com/8o9luS
language:
C++14 (clang 8.0)
created:
1 day 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!