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: