Painter partition problem!

#1

run error in testcase 3and 4

https://ide.codingblocks.com/s/59440
pls reply fast

#2

What is the t in your code for ?
You do not have to input it.
Also in Line 8, 10, 27 you dont need to multiply with t.
Your approach is perfectly fine just try rewritting the code neatly and check for proper boundaries in loops.

#3

here t is the time
i was multiply with t because we have to do binary search on the on time not on the board

#4

you see t is not required as input, as time to paint 1 unit of board is always 1 sec.
Also first u hve to sort the boards array first and then apply binary search on the sum of left portion and right portion of board from the mid u obtain everytime.
When u have obtained the rightmost point where sum of left portion of boards is <= sum of right boards then u have obtained ur anawer and it is the sum of all boards on right from that point.
.
Please try the question again now. :blush:

#5

Hi Atmanand, as you are not responding to this thread, I am marking your doubt as Resolved for now. Re-open it if required.

Please mark your doubts as resolved in your course’s “ Ask Doubt ” section, when your doubt is resolved.

#6

#include
#include
using namespace std;

bool isPossible(long long int a[],int b,int n,long long int mid,int t){
long long int painted_board=0;
int painter = 1;
for(int i=0;i<b;i++){
if(painted_board + (a[i]*t)>mid){
painter++;
painted_board = a[i]*t;
if(painter>n || painted_board>mid){
return false;
}
}
else{
painted_board += a[i]*t;
}
}
return true;
}

int painterpartition(long long int board[],int b,int n,int t){
if(b<n) return -1;

long long int sum = 0;
long long int s = board[b-1]*t;

for(int i=0;i<b;i++){
	sum += board[i];
}

long long int e = sum*t;
long long int ans=LONG_MAX;

while(s<=e){
	long long int mid = (s+e)/2;

	if(isPossible(board,b,n,mid,t)){
		ans = min(ans,mid);
		e = mid - 1;
	}

	else{
		s = mid + 1;
	}
}
return ans%10000003;

}

int main(){
int n;
int b;
int t;
cin>>b;
cin>>n;
cin>>t;
long long int board[100000];
for(int i=0;i<b;i++){
cin>>board[i];
}
cout<<painterpartition(board,b,n,t)<<endl;
return 0;
}

Try This Code