結果
問題 |
No.1858 Gorgeous Knapsack
|
ユーザー |
|
提出日時 | 2022-10-22 13:39:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 51 ms / 2,000 ms |
コード長 | 843 bytes |
コンパイル時間 | 1,736 ms |
コンパイル使用メモリ | 203,752 KB |
最終ジャッジ日時 | 2025-02-08 11:12:21 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i = 0; i < (n); i++) using namespace std; using ll = long long; using ld = long double; int main(){ cin.tie(0); ios::sync_with_stdio(0); int N,M; cin >> N >> M; vector<pair<int,int>> J(N); for(auto &[v, w] : J) cin >> v >> w; sort(J.begin(), J.end(), [&](pair<int,int> L, pair<int,int> R) { auto [vL, wL] = L; auto [vR, wR] = R; if(vL != vR) return vL > vR; return wL < wR; }); vector<ll> dp(M + 1, 0); ll ans = 0; for(auto [v, w] : J) { vector<ll> nt = dp; for(int k = 0; k <= M; k++) { if(k + w <= M) nt[k + w] = max(nt[k + w], dp[k] + v); } swap(dp, nt); ans = max(ans, *max_element(dp.begin(), dp.end()) * v); } cout << ans << endl; }