Contest Duration: - (local time) (100 minutes) Back to Home

## B - Product Max Editorial by evima

Since the absolute values of $$a, b, c$$ and $$d$$ are large, the solution of trying all possible $$x$$ and $$y$$ will not be accepted because of TLE (Time Limit Exceeded).

Here, we are going to introduce a method that fits in the time limit by narrowing the candidates.

When $$y$$ is fixed, $$x \times y$$ is a linear function of $$x$$. By the property of linear function, when $$x$$ varies within a certain range, $$x \times y$$ becomes maximum when $$x$$ is at either leftmost or rightmost end. (It can be understood easily by drawing a graph.) This property holds for every $$y$$, so we only have to consider the cases where $$x=a$$ and $$x=b$$.

Similarly, when $$x$$ is fixed, we can see that we only have to consider the cases where $$y=c$$ and $$y=d$$.

Therefore, we only have to consider the cases where $$(x, y)$$ is $$(a,c),(a,d),(b,c)$$ or $$(b,d)$$, so one can get accepted by outputting the maximum of $$a \times c,a\times d,b\times c$$ and $$b\times d$$.

Additionally, since the absolute values of $$a, b, c$$ and $$d$$ is at most $$10^9$$, the answer can be at most $$10^{18}$$. Since it does not fit in $$32$$-bit integer type (int in C++), it is good to use $$64$$-bit integer type (long long in C++).

Sample Code（C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
long long a,b,c,d;
cin>>a>>b>>c>>d;
cout<<max(max(a*c,a*d),max(b*c,b*d))<<"\n";
}

posted:
last update: