結果
問題 | No.798 コレクション |
ユーザー |
![]() |
提出日時 | 2023-02-28 17:49:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 6 ms / 2,000 ms |
コード長 | 2,739 bytes |
コンパイル時間 | 1,775 ms |
コンパイル使用メモリ | 199,516 KB |
最終ジャッジ日時 | 2025-02-11 00:10:49 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
//#define NDEBUG#include <cstddef>#include <cstdint>#include <bits/stdc++.h>namespace n91 {using i8 = std::int_least8_t;using i32 = std::int_least32_t;using i64 = std::int_least64_t;using u8 = std::uint_least8_t;using u32 = std::uint_least32_t;using u64 = std::uint_least64_t;using isize = std::ptrdiff_t;using usize = std::size_t;class rep {const usize f, l;public:class itr {friend rep;usize i;constexpr itr(const usize x) noexcept : i(x) {}public:void operator++() noexcept { ++i; }constexpr usize operator*() const noexcept { return i; }constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }};constexpr rep(const usize first, const usize last) noexcept: f(first), l(last) {}constexpr itr begin() const noexcept { return itr(f); }constexpr itr end() const noexcept { return itr(l); }};class revrep {const usize f, l;public:class itr {friend revrep;usize i;constexpr itr(usize x) noexcept : i(x) {}public:void operator++() noexcept { --i; }constexpr usize operator*() const noexcept { return i; }constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }};constexpr revrep(usize first, usize last) noexcept : f(--first), l(--last) {}constexpr itr begin() const noexcept { return itr(l); }constexpr itr end() const noexcept { return itr(f); }};template <class T> using vec_alias = std::vector<T>;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) {return a < b ? b - a : a - b;}} // namespace n91#include <algorithm>#include <iostream>#include <utility>#include <cassert>#include <cstdint>namespace n91 {void main_() {usize n;std::cin >> n;struct item {u64 a, b;};std::vector<item> is(n);for (auto &e : is) {std::cin >> e.a >> e.b;}std::sort(is.begin(), is.end(),[](const auto &l, const auto &r) {return r.b < l.b;});static constexpr u64 INF = std::numeric_limits<u64>::max();std::vector<u64> dp(n);for (const auto i : rep(0, n)) {dp[i] = is[i].a;}const usize days = n - n / 3;for (const auto d : rep(1, days)) {u64 min = dp[d - 1];for (const auto i : rep(d, n)) {const u64 temp = dp[i];dp[i] = min + is[i].a + is[i].b*d;min = std::min(min, temp);}}std::cout << *std::min_element(dp.cbegin() + days - 1, dp.cend()) << std::endl;}} // namespace n91int main() {n91::main_();return 0;}