fork download
copy 
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #define _CRT_DISABLE_PERFCRIT_LOCKS
  3. #pragma GCC optimize("fast-math")
  4. #pragma GCC optimize("no-stack-protector") 
  5. #pragma GCC optimize("Ofast,unroll-loops")
  6. #pragma GCC target("avx,avx2,fma")
  7.  
  8. #include <bits/stdc++.h>
  9.  
  10. using namespace std;
  11.  
  12. #define v vector 
  13. #define ll long long
  14. #define umap unordered_map
  15. #define uset unordered_set
  16. #define f(array) (array).begin(), (array).end()
  17. #define b(array) (array).rbegin(), (array).rend()
  18.  
  19. bool test(const v <int>& A, int k, ll maxSum) {
  20.     int count = 1;
  21.     ll curr = 0;
  22.  
  23.     for (int num : A) {
  24.         if (curr + num > maxSum) {
  25.             count++;
  26.             curr = num;
  27.             if (count > k) {
  28.                 return false;
  29.             }
  30.         } else {
  31.             curr += num;
  32.         }
  33.     }
  34.     return true;
  35. }
  36.  
  37. signed main() { 
  38.     cin.tie(nullptr), cout.tie(nullptr) 
  39.     -> ios_base::sync_with_stdio(false);
  40.  
  41.     #define file "main"
  42.     #ifndef ONLINE_JUDGE
  43.             freopen (file ".inp", "r", stdin);
  44.             freopen (file ".out", "w", stdout);
  45.     #endif  
  46.  
  47.     int n, k;
  48.     cin >> n >> k;
  49.     v <int> A(n);
  50.     ll left = 0, right = 0;
  51.  
  52.     for (int i = 0; i < n; i++) {
  53.         cin >> A[i];
  54.         left = max(left, (ll)A[i]);
  55.         right += A[i];
  56.     }
  57.  
  58.     ll result = right;
  59.     while (left <= right) {
  60.         ll mid = (left + right) / 2;
  61.         if (test(A, k, mid)) {
  62.             result = mid;
  63.             right = mid - 1;
  64.         } else {
  65.             left = mid + 1;
  66.         }
  67.     }
  68.  
  69.     cout << result << endl;
  70.  
  71.     return 0;   
  72. }
Success #stdin #stdout 0.04s 19504KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/0zuydp
language:
C++14 (clang 8.0)
created:
15 hours 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!