Submission #370044

#	Time	Username	Problem	Language	Result	Execution time	Memory
370044		danielcm585	Discharging (NOI20_discharging)	C++14	100 / 100	179 ms	11884 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;
const ll INF = 1e18;
int n, m;
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);
}

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);
    // }

    ll query(ll x) {
        ll ret = INF;
        for (int l = 0, r = sz-1; l <= r; ) {
            int mid = (l+r)/2;
            ret = min(ret,dq[mid](x));
            if (mid+1 < sz && dq[mid+1](x) < dq[mid](x)) l = mid+1;
            else r = mid-1;
        }
        return ret;
    }

} 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);
    for (int i = 1; i <= n; i++) {
        while (m > 0 && a[st[m]] <= a[i]) m--;
        st[++m] = i;
    }
    for (int i = 1; i <= m; i++) {
        ch.insert(a[st[i]],dp[i-1]);
        dp[i] = ch.query(st[i]);
    }
    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