Submission #370041

#	Time	Username	Problem	Language	Result	Execution time	Memory
370041		danielcm585	Discharging (NOI20_discharging)	C++14	100 / 100	157 ms	18652 KiB

Discharging

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second

typedef long long ll;
typedef pair<int,int> ii;

const int N = 1e6;
int n;
int a[N+2], st[N+2];
ll dp[N+2];

struct line {
    ll m, c;

    ll operator ()(ll x) {
        return m*x + c;
    }
};

bool greaterFrac(ll a, ll b, ll c, ll d) {
    // a/b >= c/d;
    if (a/b != c/d) return a/b > c/d;
    return (a%b)*d >= (c%d)*b;
}

bool isBad(line a, line b, line c) {
    // (c1-c2)/(m2-m1) >= (c2-c3)/(m3-m2)
    return greaterFrac(a.c-b.c,b.m-a.m,b.c-c.c,c.m-b.m);
    // return greaterFrac(c.c-a.c,a.m-c.m,b.c-a.c,a.m-b.m);
}

struct convexHull {
    int sz;
    deque<line> dq;

    convexHull(): sz(0) {}

    void insert(ll m, ll c) {
        line cur = {m,c};
        while (sz >= 2 && isBad(dq[sz-2],dq[sz-1],cur)) {
            dq.pop_back();
            sz--;
        }
        dq.push_back(cur);
        sz++;
    }

    ll query(ll x) {
        while (sz >= 2 && dq[0](x) >= dq[1](x)) {
            dq.pop_front();
            sz--;
        }
        return dq[0](x);
    }

} ch;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    reverse(a+1,a+n+1);
    vector<int> st;
    for (int i = 1; i <= n; i++) {
        while (!st.empty() && a[st.back()] <= a[i]) st.pop_back();
        st.push_back(i);
    }
    int m = st.size();
    // cout << m << '\n';
    // for (int i : st) cout << i << ' ';
    // cout << '\n';
    for (int i = 1; i <= m; i++) {
        ch.insert(a[st[i-1]],dp[i-1]);
        dp[i] = ch.query(st[i-1]);
        // cout << dp[i] << ' ';
    }
    // cout << '\n';
    cout << dp[m] << '\n';
    return 0;
}

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