結果
問題 | No.54 Happy Hallowe'en |
ユーザー |
![]() |
提出日時 | 2022-02-21 18:08:19 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 216 ms / 5,000 ms |
コード長 | 1,152 bytes |
コンパイル時間 | 2,653 ms |
コンパイル使用メモリ | 141,156 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-29 22:09:47 |
合計ジャッジ時間 | 4,695 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 |
ソースコード
#include <cassert>#include <cmath>#include <algorithm>#include <iostream>#include <iomanip>#include <climits>#include <map>#include <queue>#include <set>#include <cstring>#include <vector>using namespace std;typedef long long ll;struct Candy {int v;int t;Candy(int v = -1, int t = -1) {this->v = v;this->t = t;}bool operator<(const Candy &n) const {return v + t < (n.v + n.t);}};int main() {int N;cin >> N;for (int i = 0; i < N; ++i) {}vector<Candy> candy_list;for (int i = 0; i < N; ++i) {int v, t;cin >> v >> t;candy_list.push_back(Candy(v, t));}sort(candy_list.begin(), candy_list.end());int dp[10010];memset(dp, -1, sizeof(dp));dp[0] = 0;int ans = 0;for (int i = 0; i < candy_list.size(); ++i) {Candy candy = candy_list[i];for (int v = 10000; v >= 0; --v) {if (dp[v] == -1) continue;int nv = v + candy.v;int cnt = candy.v;if (v >= candy.t) cnt = 1;nv = min(nv, 10000);dp[nv] = max(dp[nv], dp[v] + cnt);ans = max(ans, dp[nv]);}}cout << ans << endl;return 0;}