fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fast_io                       \
  3.     ios_base::sync_with_stdio(false); \
  4.     cin.tie(NULL)
  5. #define clr(a, h) memset(a, (h), sizeof(a))
  6. #define all(a) (a).begin(), (a).end()
  7. #define rall(a) (a).rbegin(), (a).rend()
  8. #define sz(x) (int)x.size()
  9. #define pb push_back
  10. #define pf push_front
  11. #define ps insert
  12. #define ll long long
  13. #define ull unsigned long long
  14. #define ld long double
  15. #define PI acos(-1)
  16. #define F first
  17. #define S second
  18. #define executeTime cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  19. #define print(a) for (auto x : a) cout << x << " "; cout << "\n"
  20.  
  21. using namespace std;
  22.  
  23. typedef pair<int, int> ii;
  24. typedef vector<int> vi;
  25. typedef vector<ii> vii;
  26. typedef vector<ll> vll;
  27.  
  28. const int MOD = 1000000000 + 7;
  29. const int N = 100000 + 10;
  30. const int oo = 1e9;
  31.  
  32. ll a[N];
  33. ll n, k;
  34.  
  35. bool ok(ll cur) {
  36.     ll sum = 0ll, ans = 1ll;
  37.     for(int i = 0; i < n; i++) {
  38.         if(a[i] > cur) return 0;
  39.         sum += a[i];
  40.         if(sum > cur) {
  41.             ans += 1;
  42.             sum = a[i];
  43.         }
  44.     }
  45.     if(ans <= k) return 1;
  46.     return 0;
  47. }
  48.  
  49.  
  50. int main(){
  51.     #ifndef ONLINE_JUDGE
  52.         freopen("input.txt", "r", stdin);
  53.         freopen("output.txt", "w", stdout);
  54.     #endif
  55.     cin >> n;
  56.     for(int i = 0; i < n; i++)
  57.         cin >> a[i];
  58.     cin >> k;
  59.     ll low = 0, high = 1e14;
  60.     while(high - low > 1) {
  61.         ll mid = (low + high) >> 1;
  62.         if(ok(mid)) high = mid;
  63.         else low = mid;
  64.     }
  65.     cout << high << "\n";
  66.     return 0;
  67. }
  68.  
Success #stdin #stdout 0s 5296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
100000000000000
https://ideone.com/agaLNz
language:
C++ (gcc 8.3)
created:
38 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!