結果
問題 | No.54 Happy Hallowe'en |
ユーザー |
|
提出日時 | 2015-10-20 17:21:34 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 298 ms / 5,000 ms |
コード長 | 1,350 bytes |
コンパイル時間 | 980 ms |
コンパイル使用メモリ | 92,852 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-15 17:13:53 |
合計ジャッジ時間 | 3,399 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 |
ソースコード
#include <iostream>#include <iomanip>#include <vector>#include <algorithm>#include <numeric>#include <functional>#include <cmath>#include <queue>#include <stack>#include <set>#include <map>#include <sstream>#include <string>#define repd(i,a,b) for (int i=(a);i<(b);i++)#define rep(i,n) repd(i,0,n)#define var auto#define mod 1000000007#define inf 2147483647typedef long long ll;using namespace std;int inputValue(){int a;cin >> a;return a;}template <typename T>void output(T a, int precision) {if(precision > 0){cout << fixed << setprecision(precision) << a << "\n";}else{cout << a << "\n";}}// end of templateint main() {// source codeint N = inputValue();vector<pair<int, int>> T(N);rep(i, N){int v = inputValue(); // もらえる量int t = inputValue(); // 閾値T[i] = make_pair(t + v, t);}sort(T.begin(), T.end());vector<int> dp(20000, 0);int ret = 0;dp[0] = 1;rep(i, N){var tmp = dp;rep(j, dp.size()){if (tmp[j] && j < T[i].second) {dp[j + T[i].first - T[i].second] = 1;ret = max(ret, j + T[i].first - T[i].second);}}}output(ret, 0);return 0;}