ZCO Smart Phone

Hey i am having this problem with my code. It runs on my test cases and the sample ones but when i submit it, it gives right answer for only a handful.

#include<bits/stdc++.h>

using namespace std;

int main()

{

int n;

cin >> n;
int a[n];
for(int i = 0; i< n; i++)
{
	cin >> a[i];
}
sort(a, a+n);
long long max = 0;
for(int i = 0; i < n; i++)
{
	long long c = a[i]*(n-i);
	if(max < c)
	{
		max = c;
	}		
}
cout << max;	
return 0;

}

You are experiencing an overflow in the following line.

long long c = a[i]*(n-i);

Even though variable c is of type long long, the data type of a[i], n, and i is int and since n <= 5*10^5 and a[i] <= 10^8, the value of the above expression can easily overflow int.

So, either change the data type of a[i], n, and i to long long or change the above expression to:

long long c = (long long) a[i] * (n-i);

This way, the value of that expression will be promoted to long long and overflow will not occur.

You can read @vijju123 's answer in the following thread about the same issue.

https://discuss.codechef.com/questions/106144/data-type-of-a-expression

2 Likes

When you are defining the array, you use

int array[n];

but since the budget can be upto 10**8, you need to use at least a long for this.

Try:

long array[n]; or long long array[n];

Otherwise, you’ll have an integer overflow.

thanks it worked