結果

問題 No.3023 Utility is Max?
ユーザー ArcAki
提出日時 2025-02-01 18:03:44
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,452 bytes
コンパイル時間 3,541 ms
コンパイル使用メモリ 66,212 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2025-02-01 18:03:55
合計ジャッジ時間 9,182 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 1 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

// GPTo3-mini-highによる2回目の試行

#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) 自店での予算消化（必ず予算をぴったり使う）
        if(A1 * X1 + B1 * Y1 != I) ok = false;
        if(A2 * X2 + B2 * Y2 != I) ok = false;
 
        // (2) 他店の予算条件下で購入可能ならば「境界にある」必要がある
        ll cross1 = A2 * X1 + B2 * Y1; // 店1の指定量を店2の価格で買えるか？
        bool cross1_feasible = (cross1 <= I);
        if(cross1_feasible && cross1 != I) ok = false;
 
        ll cross2 = A1 * X2 + B1 * Y2; // 店2の指定量を店1の価格で買えるか？
        bool cross2_feasible = (cross2 <= I);
        if(cross2_feasible && cross2 != I) ok = false;
 
        // (3) 両方の指定量が互いの店の予算制約下で購入可能なら，
        //     両店で最適解として同じ満足度を実現するため，
        //     それらの消費量の組は f の厳密単調性と矛盾しないようでなければならない．
        if(cross1_feasible && cross2_feasible){
            // もし店の価格が同一なら，最適解は一意のはずなので，
            // 指定量も同一でなければならない．
            if(A1 == A2 && B1 == B2){
                if(X1 != X2 || Y1 != Y2) ok = false;
            } else {
                // 両方の店で予算の境界にあるなら，
                // f(X1,Y1)=f(X2,Y2) を実現するには
                // (X1,Y1) と (X2,Y2) はどちらか一方の成分だけ大きくなっていてはならず，
                // つまり， (X1,Y1) と (X2,Y2) が互いに「比較不能」である必要がある．
                // 具体的には，もし X1 < X2 なら Y1 > Y2，
                // または X1 > X2 なら Y1 < Y2，
                // あるいは全く同じ場合のみ可能です．
                if( !((X1 == X2 && Y1 == Y2) || (X1 < X2 && Y1 > Y2) || (X1 > X2 && Y1 < Y2)) )
                    ok = false;
            }
        }
 
        cout << (ok ? "Yes" : "No") << "\n";
    }
    return 0;
}
0