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.