結果
問題 | No.951 【本日限定】1枚頼むともう1枚無料! |
ユーザー |
|
提出日時 | 2019-12-14 00:07:08 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 140 ms / 2,000 ms |
コード長 | 1,048 bytes |
コンパイル時間 | 1,693 ms |
コンパイル使用メモリ | 175,824 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-27 22:33:56 |
合計ジャッジ時間 | 7,006 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 52 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i, n) for (int i = 0; i < (n); i++) #define repr(i, n) for (int i = (n) - 1; i >= 0; i--) #define range(a) a.begin(), a.end() void chmax(int &x, int y) { x = max(x, y); } int main() { int N, K; cin >> N >> K; vector<int> P(N), D(N); rep(i, N) cin >> P[i] >> D[i]; vector<int> ord(N); rep(i, N) ord[i] = i; sort(range(ord), [&](int i, int j) { return P[i] < P[j]; }); const int inf = 1e9; vector<int> dp0(K + 1, -inf); vector<int> dp1(K + 1, -inf); dp0[0] = 0; for (int i : ord) { vector<int> ep0(K + 1, -inf); vector<int> ep1(K + 1, -inf); for (int j = 0; j <= K; j++) { chmax(ep0[j], dp0[j]); chmax(ep1[j], dp1[j]); chmax(ep1[j], dp0[j] + D[i]); if (j + P[i] <= K) { chmax(ep0[j + P[i]], dp0[j] + D[i]); chmax(ep0[j + P[i]], dp1[j] + D[i]); } } dp0 = ep0; dp1 = ep1; } int ans = -inf; for (int i = 0; i <= K; i++) { chmax(ans, dp0[i]); } cout << ans << endl; }