fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. bool fun(int mid, vector<int>arr,int m){
  4.     int sum=0,count=0;
  5.         for(int i=0;i<arr.size();i++){
  6.             if(arr[i]>mid){
  7.                 return false;
  8.             }
  9.             else if(sum+arr[i]<=mid){
  10.                 sum+=arr[i];
  11.  
  12.             }
  13.             else{
  14.                 sum=arr[i];//why is this needed..why not write sum=0;
  15.                 count++;
  16.             }
  17.         }
  18.         return count+1<=m;
  19. }
  20. int main()
  21. {
  22.     vector<int>arr={5, 3, 20, 16, 18, 1, 10, 10, 9, 8};
  23.     int n=arr.size();
  24.     int m=3;
  25.     int ans=-1;
  26.     int l=1;
  27.     int h=accumulate(arr.begin(),arr.end(),0);
  28.  
  29.     while(l<=h){
  30.            int mid=l+(h-l)/2;
  31.            //cout<<"mid"<<mid<<endl;
  32.            if(fun(mid,arr,m)){
  33.                ans=mid;
  34.                h=mid-1;
  35.            }
  36.            else{
  37.                l=mid+1;
  38.            }
  39.            //cout<<"ans"<<ans<<endl;
  40.     }
  41.     cout<<ans<<endl;
  42.     return 0;
  43. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
37
https://ideone.com/6Uurhy
language:
C++ (gcc 8.3)
created:
8 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!