Submission #1214252

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214252		VMaksimoski008	Discharging (NOI20_discharging)	C++20	100 / 100	698 ms	129528 KiB

Discharging

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1e18;

struct line {
    ll m, b;
    ll operator()(ll x) { return m * x + b; }
};

vector<ll> cmp;
struct li_chao {
    int n;
    vector<line> tree;
    li_chao(int _n) : n(_n), tree(4*n, { 0, inf }) {}

    void add(int u, int tl, int tr, line seg) {
        if(tl + 1 == tr) {
            if(seg(cmp[tl]) < tree[u](cmp[tl])) tree[u] = seg;
            return ;
        }

        int tm = (tl + tr) / 2;
        if(tree[u].m < seg.m) swap(tree[u], seg);
        if(tree[u](cmp[tm]) > seg(cmp[tm])) {
            swap(tree[u], seg);
            add(2*u, tl, tm, seg);
        } else {
            add(2*u+1, tm, tr, seg);
        }
    }

    ll get(int u, int tl, int tr, int p) {
        if(tl + 1 == tr) return tree[u](cmp[p]);
        int tm = (tl + tr) / 2;
        if(p < tm) return min( tree[u](cmp[p]), get(2*u, tl, tm, p) );
        return min( tree[u](cmp[p]), get(2*u+1, tm, tr, p) );
    }

    void add(line seg) { add(1, 0, n, seg); }
    ll get(int p) { return get(1, 0, n, p); }
};

signed main() {
    int n; cin >> n;
    set<int> st;
    vector<int> a(n+1);
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        st.insert(a[i]);
    }

    int m = st.size();
    cmp = vector<ll>(st.begin(), st.end());

    li_chao cht(m);
    vector<ll> dp(n+1, 1e18); dp[0] = 0;

    int mx=0, j=1;
    for(int i=1; i<=n; i++) {
        if(a[i] > a[mx]) mx = i;
        while(j <= i) { cht.add({ n-j+1, dp[j-1] }); j++; }
        int p = lower_bound(cmp.begin(), cmp.end(), a[mx]) - cmp.begin();
        dp[i] = cht.get(p);
    }

    cout << dp[n] << '\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