fork(2) download
copy 
  1. #include <iostream>
  2. #include <sstream>
  3. #include <iomanip>
  4. #include <cstdio>
  5. #include <cmath>
  6. #include <cstdlib>
  7. #include <ctime>
  8. #include <utility>
  9. #include <memory.h>
  10. #include <vector>
  11. #include <list>
  12. #include <map>
  13. #include <set>
  14. #include <queue>
  15. #include <deque>
  16. #include <stack>
  17. #include <bitset>
  18. #include <algorithm>
  19. #include <functional>
  20. #include <numeric>
  21.  
  22. #define forn(i, n) for (int i = 0; i < (int)n; i++)
  23. #define forkn(i, k, n) for (int i = k; i < (int)n; i++)
  24. #define forit(i, a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); i++)
  25. #define sz(a) ((int)(a).size())
  26. #define pb push_back
  27. #define mp make_pair
  28. #define fi first
  29. #define se second
  30.  
  31. using namespace std;
  32.  
  33. typedef long long ll;
  34. typedef vector <int> vi;
  35. typedef vector <ll> vll;
  36. typedef vector <string> vs;
  37. typedef pair <int,int> pii;
  38. typedef pair <string,int> psi;
  39. typedef map <string,int> msi;
  40.  
  41. template <class T> void relax(T &a, T b) { a = min(a, b); }
  42. template <class T> void mrelax(T &a, T b) { a = max(a, b); }
  43.  
  44. const int N = 100010;
  45.  
  46. int n, k;
  47. ll s[N];
  48.  
  49. bool can(ll x)
  50. {
  51. 	int cnt = 1, b = 0;
  52. 	ll c = x;
  53.  
  54. 	forn(i, n)
  55. 	{
  56. 		if (x < s[n-i-1])
  57. 			return false;
  58. 		if (b == 2 || c < s[n-i-1])
  59. 			c = x, cnt++, b = 0;
  60.  
  61. 		c -= s[n-i-1], ++b;
  62. 	}
  63.  
  64. 	return cnt <= k;
  65. }
  66.  
  67. int main()
  68. {
  69. /*
  70.     freopen("input.txt", "rt", stdin);
  71.     freopen("output.txt", "wt", stdout);
  72. */
  73. 	cin >> n >> k;
  74. 	forn(i, n) cin >> s[i];
  75.  
  76. 	ll l = s[n-1], r = l * n, m;
  77.  
  78. 	while (l < r)
  79. 	{
  80. 		m = (l + r) >> 1;
  81.  
  82. 		if (can(m))
  83. 			r = m;
  84. 		else
  85. 			l = m + 1;
  86. 	}
  87.  
  88. 	while (can(r)) --r;
  89.  
  90. 	cout << r + 1 << "\n";
  91.  
  92.     return 0;
  93. }
Success #stdin #stdout 0s 4244KB
comments (?)
stdin
copy 
2 1
2 5
stdout
copy 
7
https://ideone.com/WqYPZT
language:
C++ (gcc 8.3)
created:
8 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!