#839750 (C++17) No.409 ダイエット

提出ソース

結果

問題	No.409 ダイエット
ユーザー	hedwig100
提出日時	2023-02-12 13:24:03
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	94 ms / 2,000 ms
コード長	7,499 bytes
コンパイル時間	2,218 ms
コンパイル使用メモリ	207,144 KB
実行使用メモリ	11,656 KB
最終ジャッジ日時	2023-09-23 05:09:31
合計ジャッジ時間	7,737 ms
ジャッジサーバーID （参考情報）	judge11 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,376 KB
testcase_01	AC	2 ms 4,376 KB
testcase_02	AC	1 ms 4,380 KB
testcase_03	AC	1 ms 4,376 KB
testcase_04	AC	1 ms 4,376 KB
testcase_05	AC	1 ms 4,376 KB
testcase_06	AC	2 ms 4,376 KB
testcase_07	AC	2 ms 4,380 KB
testcase_08	AC	2 ms 4,380 KB
testcase_09	AC	2 ms 4,376 KB
testcase_10	AC	2 ms 4,376 KB
testcase_11	AC	1 ms 4,380 KB
testcase_12	AC	2 ms 4,376 KB
testcase_13	AC	1 ms 4,376 KB
testcase_14	AC	1 ms 4,376 KB
testcase_15	AC	1 ms 4,380 KB
testcase_16	AC	2 ms 4,376 KB
testcase_17	AC	2 ms 4,380 KB
testcase_18	AC	1 ms 4,380 KB
testcase_19	AC	1 ms 4,380 KB
testcase_20	AC	1 ms 4,380 KB
testcase_21	AC	2 ms 4,376 KB
testcase_22	AC	2 ms 4,376 KB
testcase_23	AC	1 ms 4,376 KB
testcase_24	AC	2 ms 4,380 KB
testcase_25	AC	1 ms 4,376 KB
testcase_26	AC	2 ms 4,376 KB
testcase_27	AC	2 ms 4,376 KB
testcase_28	AC	1 ms 4,376 KB
testcase_29	AC	1 ms 4,376 KB
testcase_30	AC	1 ms 4,376 KB
testcase_31	AC	1 ms 4,376 KB
testcase_32	AC	2 ms 4,380 KB
testcase_33	AC	1 ms 4,376 KB
testcase_34	AC	2 ms 4,376 KB
testcase_35	AC	2 ms 4,376 KB
testcase_36	AC	2 ms 4,376 KB
testcase_37	AC	2 ms 4,376 KB
testcase_38	AC	2 ms 4,380 KB
testcase_39	AC	2 ms 4,376 KB
testcase_40	AC	2 ms 4,376 KB
testcase_41	AC	2 ms 4,376 KB
testcase_42	AC	2 ms 4,376 KB
testcase_43	AC	2 ms 4,376 KB
testcase_44	AC	2 ms 4,376 KB
testcase_45	AC	2 ms 4,376 KB
testcase_46	AC	2 ms 4,380 KB
testcase_47	AC	2 ms 4,380 KB
testcase_48	AC	2 ms 4,380 KB
testcase_49	AC	2 ms 4,376 KB
testcase_50	AC	2 ms 4,376 KB
testcase_51	AC	2 ms 4,380 KB
testcase_52	AC	2 ms 4,376 KB
testcase_53	AC	2 ms 4,376 KB
testcase_54	AC	2 ms 4,380 KB
testcase_55	AC	40 ms 6,900 KB
testcase_56	AC	27 ms 7,556 KB
testcase_57	AC	87 ms 11,656 KB
testcase_58	AC	35 ms 6,656 KB
testcase_59	AC	50 ms 7,180 KB
testcase_60	AC	31 ms 6,164 KB
testcase_61	AC	76 ms 10,460 KB
testcase_62	AC	81 ms 11,476 KB
testcase_63	AC	73 ms 9,800 KB
testcase_64	AC	37 ms 6,700 KB
testcase_65	AC	73 ms 8,868 KB
testcase_66	AC	83 ms 10,872 KB
testcase_67	AC	63 ms 9,276 KB
testcase_68	AC	48 ms 7,296 KB
testcase_69	AC	72 ms 9,628 KB
testcase_70	AC	76 ms 9,804 KB
testcase_71	AC	41 ms 7,012 KB
testcase_72	AC	94 ms 11,388 KB
testcase_73	AC	83 ms 9,344 KB
testcase_74	AC	53 ms 7,972 KB
testcase_75	AC	84 ms 9,820 KB
testcase_76	AC	61 ms 8,856 KB
testcase_77	AC	38 ms 5,932 KB
testcase_78	AC	46 ms 7,560 KB
testcase_79	AC	36 ms 6,316 KB
testcase_80	AC	89 ms 11,332 KB
testcase_81	AC	83 ms 9,700 KB
testcase_82	AC	62 ms 8,724 KB
testcase_83	AC	66 ms 8,904 KB
testcase_84	AC	52 ms 6,904 KB
testcase_85	AC	6 ms 4,376 KB
testcase_86	AC	51 ms 6,964 KB
testcase_87	AC	77 ms 9,908 KB
testcase_88	AC	29 ms 5,436 KB
testcase_89	AC	55 ms 6,480 KB
testcase_90	AC	26 ms 4,896 KB
testcase_91	AC	59 ms 6,692 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL_
void debug_out() {
    cerr << "\033[0m" << endl;
}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << ' ' << H << ',';
    debug_out(T...);
}
#define debug(...) cerr << "\033[1;36m" << __func__ << ":L" << __LINE__ << " " << #__VA_ARGS__ << ":", debug_out(__VA_ARGS__)
#define dump(x) cerr << __func__ << ":L" << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define irep(i, n) for (int i = (int)(n)-1; i >= 0; --i)

using ll  = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

constexpr int INF        = 1000'000'000;
constexpr long long HINF = 4000'000'000000'000'000;
constexpr long long MOD  = 1000000007; // = 998244353;
constexpr double EPS     = 1e-6;
constexpr double PI      = 3.14159265358979;

#pragma region Macros
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    os << '(' << p.first << ',' << p.second << ')';
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    os << '[';
    for (auto &e : v) {
        os << e << ',';
    }
    os << ']';
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &st) {
    os << '{';
    for (auto itr = st.begin(); itr != st.end(); itr++) {
        os << *itr << ',';
    }
    os << '}';
    return os;
}
template <typename K, typename V>
ostream &operator<<(ostream &os, const map<K, V> &mp) {
    os << '{';
    for (auto itr = mp.begin(); itr != mp.end(); itr++) {
        os << itr->first << ": " << itr->second << ',';
    }
    os << '}';
    return os;
}

void yn(bool cond, string Yes = "Yes", string No = "No") {
    cout << (cond ? Yes : No) << '\n';
}

template <typename T>
bool chmax(T &x, const T &y) {
    return (x < y) ? (x = y, true) : false;
}

template <typename T>
bool chmin(T &x, const T &y) {
    return (x > y) ? (x = y, true) : false;
}

template <typename T>
vector<int> id_sort(const vector<T> &A) {
    vector<pair<T, int>> B(A.size());
    for (int i = 0; i < (int)A.size(); i++) {
        B[i] = make_pair(A[i], i);
    }
    sort(B.begin(), B.end());
    vector<int> ans(A.size());
    for (int i = 0; i < (int)A.size(); i++) {
        ans[i] = B[i].second;
    }
    return ans;
}

#pragma endregion

// 幾何ライブラリのLineと名前が被る恐れがあるのでnamespaceを使う.
namespace _cht {

// Line
// 直線を管理する構造体
template <typename T>
struct Line {
    T a, b;
    Line(T a = 0, T b = 0) : a(a), b(b) {}
    T f(T x) {
        return a * x + b;
    }
    bool operator<(const Line<T> &rhs) const {
        if (a == rhs.a) return (b < rhs.b);
        return (a < rhs.a);
    }

    // necessary
    // l1 <= *this <= l2であり, l1,l2が直線集合にあるときに自分が必要かどうか判定する関数.
    bool neccesary(const Line<T> &l1, const Line<T> &l2) const {
        if (l1.a == a) return false;
        if (l2.a == a) return true;
        return (l2.a - a) * (b - l1.b) > (a - l1.a) * (l2.b - b);
    }
};

// ConvexHullTrickMonotone
// 追加する直線の傾きに単調性がある場合のConvexHullTrick
template <typename T, bool MIN = true>
struct ConvexHullTrickMonotone {
    int n;
    T sgn = MIN ? T(1) : T(-1);
    deque<Line<T>> lines;

    ConvexHullTrickMonotone() : n(0) {
        lines.resize(0);
    }

    // add_right
    // y = ax + bなる直線を追加する.
    // MIN = trueの場合: 任意の l \in linesに対して l.a <= a である必要がある.
    // MIN = falseの場合: 任意の l \in linesに対して a <= l.a である必要がある.
    // 計算量: 償却 O(1)
    void add_right(T a, T b) {
        Line<T> l(sgn * a, sgn * b);

        if (n <= 1) {
            lines.push_back(l);
            n++;
            return;
        }

        // lは不必要
        if (l.a == lines.back().a && l.b >= lines.back().b)
            return;

        while (n > 1 && !lines.back().neccesary(lines[n - 2], l)) {
            lines.pop_back();
            n--;
        }

        lines.push_back(l);
        n++;
        return;
    }

    // add_left
    // y = ax + bなる直線を追加する.
    // MIN = true の場合: 任意の l \in linesに対して a <= l.a である必要がある.
    // MIN = false の場合: 任意の l \in linesに対して l.a <= a である必要がある.
    // 計算量: 償却 O(1)
    void add_left(T a, T b) {
        Line<T> l(sgn * a, sgn * b);

        if (n <= 1) {
            lines.push_front(l);
            n++;
            return;
        }

        // lは不必要
        if (l.a == lines.front().a && l.b >= lines.front().b)
            return;

        while (n > 1 && !lines.front().neccesary(l, lines[1])) {
            lines.pop_front();
            n--;
        }

        lines.push_front(l);
        n++;
        return;
    }

    // query
    // min_{i=1,\dots,n} a_i x + b_i を求める.
    // 計算量: O(logn)
    // 制約: n > 0,すなわち少なくとも一つ直線が入っている.
    pair<T, Line<T>> query(T x) {
        assert(n > 0);
        int l = 0, r = n;
        while (r - l > 1) {
            int m = (r + l) / 2;
            if (lines[m - 1].f(x) >= lines[m].f(x))
                l = m;
            else
                r = m;
        }
        Line<T> ab(sgn * lines[l].a, sgn * lines[l].b);
        return make_pair(sgn * lines[l].f(x), ab);
    }
};

// // ConvexHullTrick
// // 傾きに単調性を仮定しないConvexHullTrick
// // TODO: 実装する.
// template <typename T, bool MIN = true>
// struct ConvexHullTrick {
//     int n;
//     multiset<Line<T>> lines;

//     ConvexHullTrick() : n(0) {
//         lines.resize(0);
//     }

//     // add
//     // y = ax + bを追加
//     // 制約: a,b \in T
//     // 計算量: O(logn) + 償却 O(1)
//     void add(T a, T b) {
//         auto itr = lines.insert(Line(a, b));
//         if (not_necessary(itr)) {
//             lines.erase(itr);
//             return;
//         }
//         while (next(itr) != lines.end() && not_necesssary(next(itr)))
//             lines.erase(next(itr));
//         while (itr != lines.begin() && not_necesssary(prev(itr)))
//             lines.erase(prev(itr));
//     }

//     // query
//     // min_{i \in L} a_ix + b_i を返す.
//     // 計算量: O(logn^2)
//     pair<Line<T>, T> query(T x) {
//         auto itr = lines.lower_bound();
//     }

//   private:
//     bool not_necesssary(map<T, T>::iterator l) {
//     }
// };

} // namespace _cht
using namespace _cht;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    int n;
    ll a, b, w;
    cin >> n >> a >> b >> w;
    vector<ll> D(n);
    rep(i, n) cin >> D[i];

    vector<ll> dp(n + 1, 0);
    ConvexHullTrickMonotone<ll, true> cht;

    cht.add_right(0, 0);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = cht.query(i).first + (ll)i * (i - 1) / 2 * b - (i - 1) * a + D[i - 1];
        cht.add_right(-i * b, dp[i] + i * a + (ll)i * (i + 1) * b / 2);
    }

    ll ans = HINF;
    rep(i, n + 1) {
        chmin(ans, w + dp[i] - (ll)(n - i) * a + (ll)(n - i) * (n - i + 1) / 2 * b);
        debug(ans);
    }
    cout << ans << '\n';
    return 0;
}

yukicoder

結果

テストケース

ソースコード