結果

問題 No.54 Happy Hallowe'en
ユーザー firiexpfiriexp
提出日時 2020-11-30 00:07:51
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WJ  
(最新)
AC  
(最初)
実行時間 -
コード長 1,312 bytes
最終ジャッジ日時 2023-10-11 02:41:16
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>

static const int MOD = 1000000007;
using ll = int64_t;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

template <class T, class U>
vector<T> make_v(U size, const T& init){ return vector<T>(static_cast<size_t>(size), init); }

template<class... Ts, class U>
auto make_v(U size, Ts... rest) { return vector<decltype(make_v(rest...))>(static_cast<size_t>(size), make_v(rest...)); }

template<class T> void chmin(T &a, const T &b){ a = (a < b ? a : b); }
template<class T> void chmax(T &a, const T &b){ a = (a > b ? a : b); }
using P = array<int, 2>;

int main() {
    int n;
    cin >> n;
    vector<P> v(n);
    for (int i = 0; i < n; ++i) {
        int h, p;
        cin >> p >> h;
        v[i] = {h-1, p};
    }
    sort(v.begin(), v.end(), [&](P a, P b){ return a[0]+a[1] < b[0]+b[1]; });
    vector<int> dp(20001, 0);
    dp[0] = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = v[i][0]; j >= 0; --j) {
            if(dp[j]) dp[j+v[i][1]] = 1;
        }
    }
    for (int i = 20000; i >= 0; --i) {
        if(dp[i]) return cout << i << "\n", 0;
    }
    return 0;
}
0