B - Product Max Editorial by ynymxiaolongbao
\(a,b,c,d\) の絶対値が大きいため、\(x\) や \(y\) の値を全通り試すとTLE(実行時間超過)の不正解になってしまいます。
ここでは、候補を絞ることで実行時間に間に合うようにする方法を紹介します。
\(x \times y\) は \(y\) を定数としたとき、 \(x\) の一次関数になります。一次関数の性質より、\(x\) がある範囲の中を動くとき、必ず、\(x\) が範囲の左端にあるときと右端にあるときの少なくとも一方で \(x \times y\) は最大になります。(グラフを書いてみると分かりやすいです。)これは \(y\) がどんな値のときでも成り立つため、\(x=a\) のケースと \(x=b\) のケースだけ考えれば良いです。
今度は \(x\) を定数とすると、同様に、 \(y=c\) のケースと \(y=d\) のケースだけ考えれば良いことがわかります。
したがって \((x,y)\) が \((a,c),(a,d),(b,c),(b,d)\) のケースだけを考えれば良くなり、 \(a \times c,a\times d,b\times c,b\times d\) の最大値を出力すれば正解できます。
また、\(a,b,c,d\) の絶対値が最大で \(10^9\) であるため、答えは最大で \(10^{18}\) になります。\(32\) ビット整数型(C++であればint型)に収まらないため、\(64\) ビット整数型(C++であればlong long型)などを使うと良いです。
#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: