Submission #1291517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291517		duckindog	Discharging (NOI20_discharging)	C++20	100 / 100	80 ms	12060 KiB

Discharging

#include <bits/stdc++.h>

using namespace std;

const int N = 1'000'000 + 10;
int n;
int a[N];

struct Line {
    long long a = 0, b = 0;
    Line() {};
    Line(long long a, long long b) : a(a), b(b) {}
    
    long long cal(const long long& x) { return a * x + b; }
};
    
inline bool bad(const Line& A, const Line& B, const Line& C) {
    return 1.0 * (C.b - A.b) / (A.a - C.a) < 1.0 * (B.b - A.b) / (A.a - B.a);
}

const long long MAX = 1'000'000'000'000'000'000;
struct CHT {
    vector<Line> st = {};
    int bot = 0;
    
    void addLine(const Line& cur) {
        for (; st.size() > 1 && bad(st.end()[-2], st.end()[-1], cur); st.pop_back());
        st.push_back(cur);
        bot = min(bot, (int)st.size() - 1);
    }    
    long long get(long long x) {
        if(st.empty()) return MAX;
        for (; bot < (int)st.size() - 1 && st[bot].cal(x) > st[bot + 1].cal(x); ++bot);
        return st[bot].cal(x);
    }
};

long long f[N];

int32_t main() { 
    cin.tie(0)->sync_with_stdio(0);
 
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    reverse(a + 1, a + n + 1);

    vector<int> q;
    for (int i = 1; i <= n; ++i) { 
        while (q.size() && a[q.back()] <= a[i]) q.pop_back();
        q.push_back(i);
    }

    CHT cht;
    cht.addLine({a[q[0]], 0});
    for (int i = 1; i <= (int)q.size(); ++i) { 
        f[i] = cht.get(q[i - 1]);
        if (i < (int)q.size()) cht.addLine({a[q[i]], f[i]});
    }
    
    cout << f[q.size()] << "\n";
}

• Subtask 1: 9 / 9
• Subtask 2: 13 / 13
• Subtask 3: 25 / 25
• Subtask 4: 11 / 11
• Subtask 5: 14 / 14
• Subtask 6: 28 / 28