JAVA   71
accio sum
Guest on 23rd August 2022 07:21:01 AM


  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. public class Main
  6. {
  7.     static boolean check(int[] arr ,long mid,int max){
  8.       long sum = 0;
  9.       int count = 1;
  10.       for(int i =0;i<arr.length;i++){
  11.         sum+=arr[i];
  12.         if(sum>mid){
  13.           count++;
  14.           sum = arr[i];
  15.         }
  16.         if(count>max){
  17.           return false;
  18.         }
  19.       }
  20.       return true;
  21.     }
  22.         public static void main (String[] args) throws java.lang.Exception
  23.         {
  24.                 //your code here
  25.       Scanner sc = new Scanner(System.in);
  26.       int n = sc.nextInt();
  27.       int m = sc.nextInt();
  28.       int[] arr = new int[n];
  29.       long minRange = Integer.MIN_VALUE;
  30.       long maxRange = 0;
  31.       for(int i = 0;i<n;i++){
  32.         arr[i]=sc.nextInt();
  33.         if(arr[i]>maxRange){
  34.           minRange = arr[i];
  35.         }
  36.         maxRange+=arr[i];
  37.       }
  38.       long s = minRange;
  39.       long e = maxRange;
  40.       long smallestSum = 0;
  41.       while(s<=e){
  42.         long mid = s+(e-s)/2;
  43.         if(check(arr,mid,m)){
  44.           smallestSum = mid;
  45.           e = mid-1;
  46.         }else{
  47.           s = mid+1;
  48.         }
  49.       }
  50.       System.out.println(smallestSum);
  51.         }
  52. }
Raw Paste

Login or Register to edit or fork this paste. It's free.