fork download
copy 
  1. //binary search+minimization problem
  2.  
  3. import java.io.*;
  4. import java.util.*;
  5.  
  6. class Main {
  7.     public static void main(String[] args)throws IOException {
  8.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  9.         int n=Integer.parseInt(br.readLine());
  10.         int[] arr=new int[n];
  11.         for(int i=0;i<n;i++){
  12.             arr[i]=Integer.parseInt(br.readLine());
  13.         }
  14.         int k=Integer.parseInt(br.readLine());
  15.         if(n<k) System.out.println(-1);
  16.         else{
  17.             int high=0, low=Integer.MAX_VALUE;
  18.             for(int i=0;i<n;i++){
  19.                 high+=arr[i];
  20.                 low=(arr[i]<low)?arr[i]:low;
  21.             }
  22.             int ans=Integer.MAX_VALUE;
  23.             int mid=(low+high)/2;
  24.             int flag=0;
  25.             while(low<=high){
  26.                 int[] students=new int[k];
  27.                 Arrays.fill(students,0);
  28.                 int i=0,ind=0;
  29.                 mid=(low+high)/2;
  30.                 for(i=0,ind=0;i<k;i++){
  31.                     while(ind<n&&students[i]+arr[ind]<=mid){
  32.                         students[i]+=arr[ind];
  33.                         if(students[i]==mid) flag=1;
  34.                         ind++;
  35.                     }
  36.                 }
  37.                 if(flag==1&&ind==n){
  38.                     ans=mid;
  39.                     high=mid-1;
  40.                 }
  41.                 else if(flag==1&&ind<n){
  42.                     low=mid+1;
  43.                 }
  44.                 else if(flag==0&&ind==n){
  45.                     high=mid-1;
  46.                 }
  47.                 else if(flag==0&&ind<n){
  48.                     low=mid+1;
  49.                 }
  50.                 else break;
  51.             }
  52.             if(ans==Integer.MAX_VALUE) System.out.println(-1);
  53.             else System.out.println(ans);
  54.         }
  55.         return;
  56.     }
  57. }
Success #stdin #stdout 0.07s 52988KB
comments (?)
stdin
copy 
4
12
34
67
90
2
stdout
copy 
113
https://ideone.com/lw3hiy
language:
Java (HotSpot 12)
created:
2 days 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!