Painter Problem

#1


what is wrong with this logic?

#2

I have edited your code… Try to submit it now…

#3

Screenshot (9)_LI
Screenshot (9)_LI852×156 14.2 KB

please explain the marked step.

#4

Reply!!!

#5

I would recommend you to go through online video lecture on the problem as : https://youtu.be/9BnC7orwkNA
To haved clear understanding of the problem.

#6

what’s the discrepancy?
2 test cases not passed

   #include <iostream>

#include
#define maxm 1000
#define endl ‘\n’
#define ll long long
#define IO ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;

bool isPossible(ll painter, ll board, ll length[], ll sum, ll mid){
ll painterUsed = 1;
ll boardPainted = 0;
for(ll i=0; i<board; i++){
if(boardPainted + length[i] > mid){
painterUsed++;
boardPainted = length[i];
if(painterUsed > painter)
return false;
} else
boardPainted = boardPainted + length[i];
}
return true;
}

ll partitionFun(ll painter, ll board, ll length[], ll sum){
ll ans = -1;
//binary search
ll l = length[board - 1];
//cout <<“l”<< l << endl;
ll h = sum;
//cout <<“h”<< h << endl;
while(l <= h){
ll mid = (l + h) / 2;
if(isPossible(painter, board, length, sum, mid)){
ans = mid;
h = mid - 1;
} else
l = mid + 1;
}
return ans;
}

int main(){
IO;

ll painter, board, length[maxm], sum = 0;
cin >> painter >> board;
for(ll i = 0; i < board; i++){
    cin >> length[i];
    sum += length[i];
}
cout << partitionFun(painter, board, length, sum) << endl;
return 0;

}