QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#477193#9127. Optimal Train Operationucup-team3926#WA 0ms3660kbC++206.3kb2024-07-13 23:59:572024-07-13 23:59:57

Judging History

你现在查看的是最新测评结果

  • [2024-07-13 23:59:57]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3660kb
  • [2024-07-13 23:59:57]
  • 提交

answer

/*
    author:  Maksim1744
    created: 13.07.2024 18:09:30
*/

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

#define mp   make_pair
#define pb   push_back
#define eb   emplace_back

#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())

template<typename T>             vector<T>& operator--            (vector<T> &v){for (auto& i : v) --i;            return  v;}
template<typename T>             vector<T>& operator++            (vector<T> &v){for (auto& i : v) ++i;            return  v;}
template<typename T>             istream& operator>>(istream& is,  vector<T> &v){for (auto& i : v) is >> i;        return is;}
template<typename T>             ostream& operator<<(ostream& os,  vector<T>  v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> pair<T,U>& operator--           (pair<T, U> &p){--p.first; --p.second;            return  p;}
template<typename T, typename U> pair<T,U>& operator++           (pair<T, U> &p){++p.first; ++p.second;            return  p;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second;        return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>  p){os << p.first << ' ' << p.second; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}

#ifdef HOME
#define SHOW_COLORS
#include "/mnt/c/Libs/tools/print.cpp"
#else
#define show(...) void(0)
#define debugf(fun)   fun
#define debugv(var)   var
#define mclock    void(0)
#define shows     void(0)
#define debug  if (false)
#define OSTREAM(...)    ;
#define OSTREAM0(...)   ;
#endif

const ll inf = 1e18;

ll intersect(pair<ll, ll> l1, pair<ll, ll> l2) {
    if (l1.first < l2.first) swap(l1, l2);
    // l1.first * x + l1.second = l2.first * x + l2.second
    // x = (l2.second - l1.second) / (l1.first - l2.first)
    // show(l1, l2);
    ll num = l2.second - l1.second;
    ll den = l1.first - l2.first;
    assert(den > 0);
    ll x;
    if (num > 0)
        x = num / den;
    else
        x = 0;
    return x;
}

struct Segment {
    deque<pair<ll, pair<ll, ll>>> lines;

    void push_back(pair<ll, ll> line) {
        if (lines.empty()) {
            lines.eb(0, line);
            return;
        }
        while (lines.size() >= 2 && lines.back().first >= intersect(lines[lines.size() - 2].second, line)) {
            lines.pop_back();
        }
        lines.eb(intersect(lines.back().second, line), line);
        if (lines.size() == 2 && lines[0].first == lines[1].first) lines.pop_front();
    }

    void push_front(pair<ll, ll> line) {
        if (lines.empty()) {
            lines.eb(0, line);
            return;
        }
        while (lines.size() >= 2 && lines[0].first <= intersect(line, lines[1].second)) {
            lines.pop_front();
        }
        lines.emplace_front(0, line);
        lines[1].first = intersect(lines[0].second, lines[1].second);
        // if (lines.size() == 2 && lines[0].first == lines[1].first) lines.pop_front();
    }

    int size() const {
        return lines.size();
    }

    ll eval_at(ll x) const {
        // int ind = lowb(lines, mp(x + 1, mp(-inf, -inf)));
        // show(lines);
        // show(x);
        // show(ind);
        // --ind;
        // return lines[ind].second.first * x + lines[ind].second.second;
        ll mn = inf;
        for (const auto& [p, line] : lines)
            mn = min(mn, line.first * x + line.second);
        return mn;
    }
};

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int n;
    cin >> n;
    vector<ll> c(n);
    vector<ll> a(n - 1);
    cin >> c >> a;
    a.insert(a.begin(), 0);
    a.pb(0);

    vector<Segment> segs;
    segs.eb();
    segs.back().push_back({0, 0});
    vector<pair<ll, int>> st;
    st.eb(0, 0);

    auto merge_segs = [&](int i1, int i2) -> int {
        if (i1 == -1) return i2;
        if (i2 == -1) return i1;
        show(segs[i1].lines, segs[i2].lines);

        int res;
        if (segs[i1].size() < segs[i2].size()) {
            for (int i = (int)segs[i1].size() - 1; i >= 0; --i) {
                segs[i2].push_front(segs[i1].lines[i].second);
            }
            res = i2;
        } else {
            for (int i = 0; i < segs[i2].size(); ++i) {
                segs[i1].push_back(segs[i2].lines[i].second);
            }
            res = i1;
        }
        show(segs[res].lines);
        return res;
    };

    // vector<pair<ll, pair<ll, ll>>> lines;
    Segment glob;
    glob.push_back({0, 0});

    vector<ll> dp(n + 1);
    show(c);
    show(a);
    for (int i = 1; i <= n; ++i) {
        shows;
        show(i, c[i - 1], a[i]);
        show(glob.lines);
        int i1 = -1;
        while (!st.empty() && st.back().first <= c[i - 1]) {
            i1 = merge_segs(st.back().second, i1);
            st.pop_back();
        }
        while (!glob.lines.empty() && glob.lines.back().second.first <= c[i - 1])
            glob.lines.pop_back();
        show(glob.lines);
        show(st);
        if (i1 != -1) {
            show(segs[i1].lines);
            st.eb(c[i - 1], i1);
            glob.push_back({c[i - 1], segs[i1].eval_at(c[i - 1])});
        }
        show(glob.lines);
        show(glob.eval_at(i));
        dp[i] = glob.eval_at(i) + a[i];
        segs.eb();
        segs.back().push_back({-i, dp[i]});
        st.eb(0, segs.size() - 1);
    }

    show(dp);
    cout << dp[n] << '\n';

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3568kb

input:

4
3 1 4 1
5 9 2

output:

15

result:

ok "15"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

9
28 35 19 27 84 98 78 79 60
40 35 54 63 72 71 27 94

output:

682

result:

ok "682"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

7
476190629 262703497 211047202 971407775 628894325 731963982 822804784
877914575 602436426 24979445 861648772 623690081 433933447

output:

5339182432

result:

ok "5339182432"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3624kb

input:

8
910286918 802329211 404539679 303238506 317063340 492686568 773361868 125660016
430302156 982631932 161735902 880895728 923078537 707723857 189330739

output:

6311516364

result:

wrong answer 1st words differ - expected: '6166732840', found: '6311516364'