結果
問題 | No.974 最後の日までに |
ユーザー | noshi91 |
提出日時 | 2020-01-17 21:54:58 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 106 ms / 2,000 ms |
コード長 | 4,646 bytes |
コンパイル時間 | 1,028 ms |
コンパイル使用メモリ | 90,396 KB |
実行使用メモリ | 23,408 KB |
最終ジャッジ日時 | 2024-04-14 21:43:56 |
合計ジャッジ時間 | 6,021 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 87 ms
22,084 KB |
testcase_01 | AC | 85 ms
22,208 KB |
testcase_02 | AC | 88 ms
22,212 KB |
testcase_03 | AC | 89 ms
22,280 KB |
testcase_04 | AC | 86 ms
22,476 KB |
testcase_05 | AC | 86 ms
23,024 KB |
testcase_06 | AC | 87 ms
22,212 KB |
testcase_07 | AC | 89 ms
22,212 KB |
testcase_08 | AC | 90 ms
22,084 KB |
testcase_09 | AC | 88 ms
21,956 KB |
testcase_10 | AC | 89 ms
21,956 KB |
testcase_11 | AC | 87 ms
21,956 KB |
testcase_12 | AC | 88 ms
21,956 KB |
testcase_13 | AC | 90 ms
22,796 KB |
testcase_14 | AC | 88 ms
22,800 KB |
testcase_15 | AC | 87 ms
21,956 KB |
testcase_16 | AC | 87 ms
22,088 KB |
testcase_17 | AC | 105 ms
22,208 KB |
testcase_18 | AC | 106 ms
22,084 KB |
testcase_19 | AC | 105 ms
22,088 KB |
testcase_20 | AC | 106 ms
21,960 KB |
testcase_21 | AC | 104 ms
22,084 KB |
testcase_22 | AC | 103 ms
22,080 KB |
testcase_23 | AC | 105 ms
22,212 KB |
testcase_24 | AC | 103 ms
21,956 KB |
testcase_25 | AC | 2 ms
6,940 KB |
testcase_26 | AC | 2 ms
6,944 KB |
testcase_27 | AC | 73 ms
22,320 KB |
testcase_28 | AC | 88 ms
23,236 KB |
testcase_29 | AC | 2 ms
6,940 KB |
testcase_30 | AC | 105 ms
21,956 KB |
testcase_31 | AC | 2 ms
6,940 KB |
testcase_32 | AC | 2 ms
6,944 KB |
testcase_33 | AC | 57 ms
15,120 KB |
testcase_34 | AC | 92 ms
21,952 KB |
testcase_35 | AC | 2 ms
6,940 KB |
testcase_36 | AC | 2 ms
6,940 KB |
testcase_37 | AC | 106 ms
23,408 KB |
testcase_38 | AC | 2 ms
6,940 KB |
testcase_39 | AC | 2 ms
6,940 KB |
testcase_40 | AC | 70 ms
22,192 KB |
testcase_41 | AC | 83 ms
21,956 KB |
testcase_42 | AC | 102 ms
22,084 KB |
testcase_43 | AC | 103 ms
21,956 KB |
testcase_44 | AC | 87 ms
22,060 KB |
testcase_45 | AC | 64 ms
15,124 KB |
testcase_46 | AC | 2 ms
6,944 KB |
testcase_47 | AC | 2 ms
6,940 KB |
testcase_48 | AC | 2 ms
6,940 KB |
testcase_49 | AC | 2 ms
6,940 KB |
testcase_50 | AC | 2 ms
6,944 KB |
testcase_51 | AC | 2 ms
6,940 KB |
ソースコード
//#define NDEBUG #include <algorithm> #include <cstddef> #include <cstdint> #include <iostream> #include <utility> #include <vector> namespace n91 { using i8 = std::int_fast8_t; using i32 = std::int_fast32_t; using i64 = std::int_fast64_t; using u8 = std::uint_fast8_t; using u32 = std::uint_fast32_t; using u64 = std::uint_fast64_t; using isize = std::ptrdiff_t; using usize = std::size_t; struct rep { struct itr { usize i; constexpr itr(const usize i) noexcept : i(i) {} void operator++() noexcept { ++i; } constexpr usize operator*() const noexcept { return i; } constexpr bool operator!=(const itr x) const noexcept { return i != x.i; } }; const itr f, l; constexpr rep(const usize f, const usize l) noexcept : f(std::min(f, l)), l(l) {} constexpr auto begin() const noexcept { return f; } constexpr auto end() const noexcept { return l; } }; struct revrep { struct itr { usize i; constexpr itr(const usize i) noexcept : i(i) {} void operator++() noexcept { --i; } constexpr usize operator*() const noexcept { return i; } constexpr bool operator!=(const itr x) const noexcept { return i != x.i; } }; const itr f, l; constexpr revrep(const usize f, const usize l) noexcept : f(l - 1), l(std::min(f, l) - 1) {} constexpr auto begin() const noexcept { return f; } constexpr auto end() const noexcept { return l; } }; template <class T> auto md_vec(const usize n, const T &value) { return std::vector<T>(n, value); } template <class... Args> auto md_vec(const usize n, Args... args) { return std::vector<decltype(md_vec(args...))>(n, md_vec(args...)); } template <class T> constexpr T difference(const T &a, const T &b) noexcept { if (a < b) { return b - a; } else { return a - b; } } template <class T> void chmin(T &a, const T &b) noexcept { if (b < a) { a = b; } } template <class T> void chmax(T &a, const T &b) noexcept { if (a < b) { a = b; } } template <class F> class fix_point : private F { public: explicit constexpr fix_point(F &&f) : F(std::forward<F>(f)) {} template <class... Args> constexpr decltype(auto) operator()(Args &&... args) const { return F::operator()(*this, std::forward<Args>(args)...); } }; template <class F> constexpr decltype(auto) make_fix(F &&f) { return fix_point<F>(std::forward<F>(f)); } template <class T> T scan() { T ret; std::cin >> ret; return ret; } } // namespace n91 #include <algorithm> #include <iostream> #include <tuple> #include <utility> #include <vector> namespace n91 { void main_() { /* std::ios::sync_with_stdio(false); std::cin.tie(nullptr); //*/ const usize n = scan<usize>(); if (n == 1) { std::cout << 0 << std::endl; return; } struct day_t { i64 a; u64 b; i64 c; }; std::vector<day_t> ds(n); for (auto &e : ds) { std::cin >> e.a >> e.b >> e.c; } const usize h = n / 2; struct node { i64 co; u64 pt; bool operator<(const node &r) const { return std::tie(co, pt) < std::tie(r.co, r.pt); } }; std::vector<node> ff, fd; ff.push_back({0, 0}); for (const usize i : rep(0, h)) { const auto &d = ds[i]; std::vector<node> nff, nfd; for (const auto &e : ff) { nff.push_back({e.co + d.a, e.pt}); nfd.push_back({e.co, e.pt}); } for (const auto &e : fd) { nff.push_back({e.co - d.c, e.pt + d.b}); } ff = std::move(nff); fd = std::move(nfd); } std::vector<node> bf, bd; bf.push_back({0, 0}); for (const usize i : revrep(h, n)) { const auto &d = ds[i]; std::vector<node> nbf, nbd; for (const auto &e : bf) { nbf.push_back({e.co + d.a, e.pt}); nbd.push_back({e.co - d.c, e.pt + d.b}); } for (const auto &e : bd) { nbf.push_back({e.co, e.pt}); } bf = std::move(nbf); bd = std::move(nbd); } std::sort(ff.begin(), ff.end()); std::sort(fd.begin(), fd.end()); std::sort(bf.begin(), bf.end()); std::sort(bd.begin(), bd.end()); u64 ans = 0; { u64 pm = 0; auto itr = bf.crbegin(); for (const auto &e : ff) { while (itr != bf.crend() && itr->co + e.co >= 0) { chmax(pm, itr->pt); itr += 1; } if (itr != bf.crbegin()) chmax(ans, pm + e.pt); } } { u64 pm = 0; auto itr = bd.crbegin(); for (const auto &e : fd) { while (itr != bd.crend() && itr->co + e.co >= 0) { chmax(pm, itr->pt); itr += 1; } if (itr != bd.crbegin()) chmax(ans, pm + e.pt); } } std::cout << ans << std::endl; } } // namespace n91 int main() { n91::main_(); return 0; }