Painter partition problem

#1

sir i wrote this code. this is giving completely correct answer. but when i submit the same code then it does not passes test cases nd it shows after submission -
Dang! You couldn’t score a perfect 100 because you failed one or more testcases. This means that your program didn’t account for all input cases (did you account for negative numbers, for example?).

i m providing the link of that code here. please somebody look into it nd tell me what am i doing wrong???

#2

Look out for overflows.

1 Like
#3

@yashmalik.official sir can u please be more specific that what should i change?? how can i overcome with that overflow problem??

#4

Note that the operations such as

get_max(length, n)*t
sum*t

will lead to overflows, so use long long for these cases.

1 Like
#5

@yashmalik.official sir i made all the changes as u said but still it is not accepting. The modified code is here -


i used long long int but now it is only passing only 1 test case.
image
image1366Ă—768 93.3 KB

sir please look into this once more.

#6 
get_max(length, n)*t

will still result in an overflow (because both are of type int), either make everything long long or do,

(long long)get_max(length, n)*t
(long long)sum*t
#7

@yashmalik.official sir still unable to score 100. i used everywhere long long int as u said. sir can u please make the changes in the above code which i sent to u. it would be very helpful and clear too :thinking: :thinking:

#8 
#include <iostream>
#include <climits>
using namespace std;

#define int long long

int get_max(int arr[], int n);
bool isPossible(int arr[], int n, int painters, int t, int cur_time);


int32_t main()
{
	int n, k, t;
	int sum = 0;
	cin >> n >> k >> t;
	int length[n];
	for (int i = 0; i < n; ++i)
	{
		cin >> length[i];
		sum += length[i];
	}
	int start = get_max(length, n) * t, end = sum * t, ans = 0;
	while (start <= end)
	{
		int mid = (start + end) / 2;
		if (isPossible(length, n, k, t, mid))
		{
			end = mid - 1;
			ans = mid;
		}
		else {
			start = mid + 1;
		}
	}

	cout << ans % 10000003 << endl;

	return 0;
}


int get_max(int arr[], int n)
{
	int x = INT_MIN;
	for (int i = 0; i < n; ++i) {
		x = max(x, arr[i]);
	}
	return x;
}
bool isPossible(int arr[], int n, int painters, int t, int cur_time)
{
	int painters_req = 1, sum = 0;
	for (int i = 0; i < n; ++i)
	{
		sum += arr[i];
		if (sum * t > cur_time)
		{
			++painters_req;
			sum = arr[i];
		}
	}
	if (painters_req <= painters) {
		return true;
	}
	else { return false; }
}
1 Like
#9

@yashmalik.official thank u so much sir :smiley:

1 Like