1 #include <iostream> 2 #include <cstdio> 3 #include <queue> 4 #include <cstring> 5 #include <algorithm> 6 7 using namespace std; 8 9 int n,m; 10 int arr[100010]; 11 int reans; 12 int flag; 13 14 void dfs(int mi,int ma) 15 { 16 if(flag==1) 17 return ; 18 if(mi==ma) 19 { 20 flag=1; 21 reans=mi; 22 return ; 23 } 24 int num=1; 25 int tmp=0; 26 int ans=(mi+ma)/2; 27 for(int i=0;i<n;i++) 28 { 29 if(tmp+arr[i]<=ans) 30 { 31 tmp=tmp+arr[i]; 32 } 33 else 34 { 35 tmp=arr[i]; 36 num++; 37 } 38 } 39 if(num>m) 40 { 41 dfs(ans+1,ma); 42 } 43 else if(num<=m) 44 { 45 dfs(mi,ans); 46 } 47 } 48 49 int main() 50 { 51 while(scanf("%d%d",&n,&m)!=EOF) 52 { 53 int ma=0; 54 for(int i=0;i<n;i++) 55 { 56 scanf("%d",&arr[i]); 57 if(arr[i]>ma) 58 ma=arr[i]; 59 } 60 flag=0; 61 dfs(ma,1000000000); 62 cout<<reans<<endl; 63 } 64 return 0; 65 }