結果

問題 No.3077 Goodstuff Deck Builder(Hard)
ユーザー Zhiyuan Chen
提出日時 2025-03-29 13:36:06
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 354 ms / 3,000 ms
コード長 969 bytes
コンパイル時間 2,321 ms
コンパイル使用メモリ 203,760 KB
実行使用メモリ 81,192 KB
最終ジャッジ日時 2025-03-29 13:36:16
合計ジャッジ時間 8,833 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 57
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)

// 假设 chmax 实现如下
template <typename T>
bool chmax(T &a, T b) { 
    if(a < b) { 
        a = b; 
        return true; 
    } 
    return false; 
}

int main(){
    int N, M;
    cin >> N >> M;
    vector<pair<int, int>> hand(N);
    rep(i, N){
        cin >> hand[i].first >> hand[i].second;
    }
    // 按卡牌的成本降序排序（费用大的先用）
    sort(hand.rbegin(), hand.rend());
    
    vector<long long> dp(M + 1, 0LL);
    // 初始状态：能量为 M 时伤害为 0（其余默认0）
    dp[M] = 0;
    // 状态转移
    for(auto [C, D] : hand){
        for (int i = C; i <= M; i++){
            int j = (i - C) >> 1; // 能量更新为 floor((i-C)/2)
            chmax(dp[j], dp[i] + D);
        }
    }
    long long ans = 0;
    for (int i = 0; i <= M; i++){
        chmax(ans, dp[i]);
    }
    cout << ans << "\n";
    return 0;
}
0