CSES Problem Array Division Solution

 

 Problem Link:  https://cses.fi/problemset/task/1085/

Solution in C++:

/// Author : AH_Tonmoy

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mx = 2e5 + 9 ;

int a[mx] , n , k ;

bool check(int x){

for ( int i = 1 ; i <= n ; i++){

if(a[i] > x ) return false ;

}

int sub_array_cnt = 1 ;

int sub_array_sum = a[1] ;

for ( int i = 2 ; i <= n ; i++){

if(sub_array_sum + a[i] <= x){

sub_array_sum += a[i] ;

}

else {

sub_array_cnt++ ;

sub_array_sum = a[i] ;

}

}

return sub_array_cnt <= k ;

}

int32_t main() {

ios_base::sync_with_stdio(0);

cin.tie(0);

cin >> n >> k ;

for ( int i = 1 ; i <= n ; i++){

cin >> a[i] ;

}

int l = 0 , r = 2e14 ;

int ans = 0 ;

while( l <= r){

int mid = ( l + r ) / 2 ;

if(check(mid)){

// cout << mid << endl ;

ans = mid ;

r = mid - 1 ;

}

else {

l = mid + 1 ;

}

}

cout << ans <<'\n';

return 0 ;

}