結果
問題 | No.54 Happy Hallowe'en |
ユーザー |
![]() |
提出日時 | 2021-12-17 12:23:37 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 163 ms / 5,000 ms |
コード長 | 709 bytes |
コンパイル時間 | 1,993 ms |
コンパイル使用メモリ | 178,352 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-14 13:18:16 |
合計ジャッジ時間 | 4,149 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 |
ソースコード
#include <bits/stdc++.h>using namespace std;int main(){int N;cin >> N;vector<int> V(N), T(N);for (int i = 0; i < N; i++){cin >> V[i] >> T[i];}vector<tuple<int, int, int>> S(N);for (int i = 0; i < N; i++){S[i] = make_tuple(V[i] + T[i], V[i], T[i]);}sort(S.begin(), S.end());for (int i = 0; i < N; i++){V[i] = get<1>(S[i]);T[i] = get<2>(S[i]);}vector<bool> dp(20000, false);dp[0] = true;for (int i = 0; i < N; i++){for (int j = T[i] - 1; j >= 0; j--){if (dp[j]){dp[j + V[i]] = true;}}}int ans = 0;for (int i = 0; i < 20000; i++){if (dp[i]){ans = max(ans, i);}}cout << ans << endl;}