結果

問題 No.3023 Utility is Max?
ユーザー ArcAki
提出日時 2025-02-01 20:12:41
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,099 bytes
コンパイル時間 882 ms
コンパイル使用メモリ 78,072 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-02-01 20:12:47
合計ジャッジ時間 4,990 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 1 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
using namespace std;
using ll = long long;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int Q; 
    cin >> Q;
    while(Q--){
        ll I; 
        cin >> I;
        ll A1, B1, X1, Y1;
        cin >> A1 >> B1 >> X1 >> Y1;
        ll A2, B2, X2, Y2;
        cin >> A2 >> B2 >> X2 >> Y2;
        
        bool ok = true;
        
        // [条件1] 自店での予算消化：必ず I と一致している必要がある
        if(A1 * X1 + B1 * Y1 != I) ok = false;
        if(A2 * X2 + B2 * Y2 != I) ok = false;
        
        // [条件2] 他店の価格で購入可能ならば、予算の余裕はあってはならない
        ll cost1_under2 = A2 * X1 + B2 * Y1; // 店2の価格で店1の注文
        if(cost1_under2 < I) ok = false;
        ll cost2_under1 = A1 * X2 + B1 * Y2; // 店1の価格で店2の注文
        if(cost2_under1 < I) ok = false;
        
        // [条件3] 両方の cross条件が成立する場合，
        //         店1では (X2,Y2) が予算内で買えるので f(X1,Y1) >= f(X2,Y2)，
        //         店2では (X1,Y1) が予算内で買えるので f(X2,Y2) >= f(X1,Y1)．
        //         よって f(X1,Y1)=f(X2,Y2) とできなければならない．
        //         厳密単調性から，もし両点が比較可能（＝一方が他方を支配）なら必ず f の値は異なるため，
        //         両点が同じか、または互いに比較不能でなければならない．
        if( (A2 * X1 + B2 * Y1 == I) && (A1 * X2 + B1 * Y2 == I) ){
            // もし店の価格が全く同じなら，予算制約も同一となるので，最適解は一意（よって同一）でなければならない
            if(A1 == A2 && B1 == B2){
                if(X1 != X2 || Y1 != Y2) ok = false;
            }
            else {
                if( !((X1 == X2 && Y1 == Y2) || (X1 < X2 && Y1 > Y2) || (X1 > X2 && Y1 < Y2)) )
                    ok = false;
            }
        }
        
        cout << (ok ? "Yes" : "No") << "\n";
    }
    return 0;
}
0