fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std; 
  3.  
  4. main(){
  5.     int t ; 
  6.     cin >> t ;
  7.     while(t--){
  8.     long long n , k ;
  9.     cin >> k >> n;
  10.  
  11.     vector<long long> arr(n) ;
  12.  
  13.     for(int i = 0; i < n; ++i)cin >> arr[i] ; 
  14.  
  15.  
  16.     long long s = *max_element(arr.begin(), arr.end()), e = (n)**max_element(arr.begin(), arr.end()) ;
  17.  
  18.     for(int i = 1; i <= n - 1; ++i){
  19.         arr[i] += arr[i-1] ;
  20.     }
  21.  
  22.     while(e > s){
  23.         long long mid = s + (e-s) / 2 ;
  24.  
  25.         long long sum = 0 ;
  26.         bool fff = false ;
  27.         for(int i = 0; i < k; ++i){
  28.             auto it = upper_bound(arr.begin(), arr.end(), sum + mid) ;
  29.             if(it == arr.end()){
  30.                 fff = true ;
  31.                 break ;
  32.             }
  33.             if(it == arr.begin())break ;
  34.             sum -= *(--it) ;
  35.             if(sum == 0)break ;
  36.             sum = *it ;
  37.         }
  38.  
  39.         if(fff)e = mid ;
  40.         else s = mid + 1 ;
  41.  
  42.     }
  43.  
  44.     cout << e << "\n" ;
  45.     }
  46.  
  47. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
1
3 10
5 3 20 16 18 1 10 10 9 8
stdout
copy 
37
https://ideone.com/YqAdwD
language:
C++ (gcc 8.3)
created:
1 year 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!