fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define sum accumulate
  3. using namespace std;
  4.  
  5. long long solve(int n, long long M, vector<long long> A) {
  6.     long long count = 0;
  7.     long long sum = 0;
  8.     int l = 0;
  9.  
  10.     for (int r = 0; r < n; ++r) {
  11.         sum += A[r];
  12.         while (sum > M && l <= r) {
  13.             sum -= A[l];
  14.             l++;
  15.         }
  16.  
  17.         count += (r - l + 1);
  18.     }
  19.  
  20.     return count;
  21. }
  22.  
  23. long long find(int n, long long k, vector<long long> A) {
  24.     long long low = *min_element(A.begin(), A.end()); 
  25.     long long high = sum(A.begin(), A.end(), 0LL);
  26.     long long res = high;
  27.     while (low <= high) {
  28.         long long mid = low + (high - low) / 2;
  29.         if (solve(n, mid, A) >= k) {
  30.             res = mid;
  31.             high = mid - 1;
  32.         } else {
  33.             low = mid + 1;
  34.         }
  35.     }
  36.  
  37.     return res;
  38. }
  39.  
  40. int main() {
  41.     int n;
  42.     long long k;
  43.     cin >> n >> k;
  44.  
  45.     vector<long long> A(n);
  46.     for (int i = 0; i < n; ++i) {
  47.         cin >> A[i];
  48.     }
  49.     cout << find(n, k, A) << endl;
  50.  
  51.     return 0;
  52. }
  53.  
Runtime error #stdin #stdout 0.04s 5296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/NiqHTA
language:
C++ (gcc 8.3)
created:
249 days ago
visibility:
secret

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!