結果

問題 No.3077 Goodstuff Deck Builder(Hard)
コンテスト
ユーザー Yotugi
提出日時 2025-04-06 23:16:56
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 2,565 bytes
コンパイル時間 3,488 ms
コンパイル使用メモリ 305,224 KB
実行使用メモリ 814,692 KB
最終ジャッジ日時 2025-04-06 23:17:05
合計ジャッジ時間 7,178 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other MLE * 1 -- * 56
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using ll = long long;
using str = string;
#define re(n) for(int _=0;_<int(n);_++)
#define rep(i,n) for(int i=0; i<int(n); i++)
#define rep1(i,s,n) for(int i=int(s); i<int(n); i++)
#define rep2(i,s,n,a) for (ll i = a; i < ll(n); i += (a))
#define per(i,n) for(int i=int(n)-1; i>=0; i--)
#define per1(i,s,n) for(int i=int(n)-1; i>=s; i--)
#define all(x) x.begin(), x.end()
#define SORT(v) sort(all(v))
#define REV(v) reverse(all(v))
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define elif else if
#define len(x) ll(x.size())
#define _GLIBCXX_DEBUG
template<typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template<typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }
template<class T>void vcin(vector<T> &n){for(int i=0;i<int(n.size());i++) cin>>n[i];}
template<class T>void vcout(vector<T> &n){for(int i=0;i<int(n.size());i++){cout<<n[i]<<" ";}cout<<endl;}
using vi = vector<int>; 
using vvi = vector<vi>;
using pii = pair<int, int>;
using vl = vector<ll>; 
using vvl = vector<vl>;
using pll = pair<ll, ll>;
using vpi = vector<pii>;
using vpl = vector<pll>;
using vc = vector<char>; 
using vs = vector<str>;
using quei = deque<int>;
using quel = deque<ll>;


#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")


int main() {
    int n, k;
    cin >> n >> k;

    int tmp = 0;
    vector<pair<int, int>> data;

    for (int i = 0; i < n; ++i) {
        int c, v;
        cin >> c >> v;
        if (c == 0) {
            tmp += v;
            continue;
        }
        data.emplace_back(c, v);
    }

    sort(data.rbegin(), data.rend());  // 降順にソート

    const int m = 20;
    vector<vector<ll>> dp(m, vector<ll>(k + 1, 0));

    vector<int> p = {1};
    for (int i = 0; i < m; ++i) {
        p.push_back(p.back() * 2);
    }

    for (auto& [c, v] : data) {
        vector<vector<ll>> ndp(m, vector<ll>(k + 1, 0));
        
        for (int i = 0; i < m; ++i) {
            ll nc = c * p[i];
            for (int j = 0; j <= k; ++j) {
                ndp[i][j] = max(ndp[i][j], dp[i][j]);
                if (i + 1 < m && j + nc <= k) {
                    ndp[i + 1][j + nc] = max(ndp[i + 1][j + nc], dp[i][j] + v);
                }
            }
        }

        dp = ndp;
    }

    ll ans = 0;
    for (const auto& row : dp) {
        for (ll val : row) {
            ans = max(ans, val);
        }
    }

    cout << ans + tmp << endl;

    return 0;
}
0