AtCoder Beginner Contest 095 Half and Half
##問題
095_C Half and Half
ファーストフードチェーン「ピザアット」のメニューは「A ピザ」「B ピザ」「AB ピザ」の3種類です。
A ピザと B ピザは全く異なるピザで、これらをそれぞれ半分に切って組み合わせたものが AB ピザです。A ピザ、B ピザ、AB ピザ 1枚あたりの値段はそれぞれ A円、B円、C円です。
中橋くんは、今夜のパーティーのために A ピザ X枚と B ピザ Y枚を用意する必要があります。
これらのピザを入手する方法は、Aピザや Bピザを直接買うか、AB ピザ 2枚を買って A ピザ 1枚と B ピザ 1枚に組み替える以外にはありません。
このためには最小で何円が必要でしょうか?なお、ピザのみ替えにより、必要な量を超えたピザが発生しても構いません。
##入力
A B C D E
##入力例1
1500 2000 1600 3 2
##出力例1
7900
##質問
O(1)での実装を試みたのですが、testケースを一つだけ通らずWAでしたのでどこに問題があるのかを教えていただけると幸いです。
模範解答を見てみましたが、0(N)での実装だったためO(1)でできるか自分で実装を試みました。
O(1)での実装
cpp
1#include <bits/stdc++.h> 2using namespace std; 3using ll = long long; 4 5int main() { 6 int A, B, C, X, Y; 7 cin >> A >> B >> C >> X >> Y; 8 9 if(C * 2 <= A && C * 2 <= B) { 10 cout << max(X, Y) * 2 * C << endl; 11 return 0; 12 } 13 14 if(C * 2 <= A + B && X >= Y) { 15 cout << min(X, Y) * 2 * C + abs(X-Y) * A << endl; 16 return 0; 17 } 18 19 if(C * 2 <= A + B && X <= Y) { 20 cout << min(X, Y) * 2 * C + abs(X-Y) * B << endl; 21 return 0; 22 } 23 24 if(C * 2 >= A + B) { 25 cout << A * X + B * Y << endl; 26 return 0; 27 } 28}
こちらは模範解答での実装です。
##補足 O(N)での実装
cpp
1#include <bits/stdc++.h> 2using namespace std; 3using ll = long long; 4using pii = pair<int, int>; 5const long long INF = 1LL << 60; 6const ll C = 1000000000+7; 7 8int main() { 9 int A, B, C, X, Y; 10 cin >> A >> B >> C >> X >> Y; 11 12 ll min_cost = INF; 13 for(int k=0; k<=100000; k++) { 14 ll cost = 2*C*k + max(0, X-k) * A + max(0, Y-k) * B; 15 min_cost = min(min_cost, cost); 16 } 17 cout << min_cost << endl; 18}
ご回答いただけると幸いです。
よろしくお願いいたします
回答2件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。