結果

問題 No.3325 陰陽師
コンテスト
ユーザー bolero
提出日時 2025-10-19 14:42:38
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,627 bytes
コンパイル時間 3,069 ms
コンパイル使用メモリ 286,116 KB
実行使用メモリ 22,576 KB
最終ジャッジ日時 2025-11-01 02:54:38
合計ジャッジ時間 40,165 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17 TLE * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

template <typename T>
enable_if_t<is_integral_v<T>, T>
bin_search(T ok, T ng, function<bool(T)> check)
{
    while (max(ok, ng) - min(ok, ng) > 1)
    {
        T mid = midpoint(ok, ng);
        (check(mid) ? ok : ng) = mid;
    }
    return ok;
}

int main()
{
    int N, M;
    cin >> N >> M;

    vector<int> S(N);
    rep(i, N)
    {
        cin >> S[i];
    }

    vector<int> T(M);
    rep(i, M)
    {
        cin >> T[i];
    }

    // n体を倒した場合の最大負担.
    // 倒せない場合はINT_MAX
    auto calc_max_loss = [&](int break_ghost_cnt) -> int
    {
        if (break_ghost_cnt == 0)
        {
            return 0;
        }

        if (M < break_ghost_cnt)
        {
            return INT32_MAX;
        }

        multiset<int> sub_S(S.begin(), S.end());

        vector<int> sub_T(T.begin(), T.begin() + break_ghost_cnt);
        sort(sub_T.begin(), sub_T.end());

        int score = 0;
        for (auto t : sub_T)
        {
            auto itr = sub_S.lower_bound(t);
            if (itr == sub_S.end())
            {
                return INT32_MAX;
            }

            score = max(score, *itr - t);
            sub_S.erase(itr);
        }

        return score;
    };

    // ghostをcnt体倒せるかどうか
    auto check_breakble = [&](int cnt) -> bool
    {
        return calc_max_loss(cnt) != INT32_MAX;
    };

    int max_breakable_ghost_cnt = bin_search<int>(0, M + 2, check_breakble);
    cout << calc_max_loss(max_breakable_ghost_cnt) << endl;

    return 0;
}
0