Submission #320535

#	Time	Username	Problem	Language	Result	Execution time	Memory
320535		arujbansal	Discharging (NOI20_discharging)	C++17	100 / 100	847 ms	285508 KiB

Discharging

#include <bits/stdc++.h>

#define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define setIO(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout)
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int) (x).size()
#define lc(i) 2*i
#define rc(i) 2*i+1
#define int long long
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vii = vector<ii>;
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
using vvb = vector<vb>;

const int N = 1e9 + 5, MOD = 1e9 + 7, INF = 1e17;

template<typename T>
struct LiChaoTree {

    struct Line {
        T slope, yIntercept;

        Line() {
            slope = 0;
            yIntercept = INF;
        }

        Line(T slope, T yIntercept) : slope(slope), yIntercept(yIntercept) {}

        T val(T x) {
            return slope * x + yIntercept;
        }
    };

    struct Node {
        int left, right;
        Line line;

        Node() {
            left = -1;
            right = -1;
        }

        T val(T x) { return line.val(x); }
    };

    T n;
    vector<Node> t;

    void init(T n) {
        this->n = n;
        t.clear();
        t.emplace_back();
        t.emplace_back();
    }

    void create_children(int i) {
        if (t[i].left > -1) return;
        t[i].left = sz(t);
        t.emplace_back();
        t[i].right = sz(t);
        t.emplace_back();
    }

    void insert(int i, T l, T r, Line newLine) {
        T mid = (l + r) >> 1;
        if (newLine.val(mid) < t[i].val(mid)) swap(newLine, t[i].line);
        if (r - l <= 1) return;
        create_children(i);
        if (newLine.val(l) <= t[i].val(l)) insert(t[i].left, l, mid, newLine);
        else insert(t[i].right, mid + 1, r, newLine);
    }

    T query(int i, T l, T r, T x) {
        if (r - l <= 1) return t[i].val(x);
        create_children(i);
        T mid = (l + r) >> 1;
        if (x <= mid) return min(t[i].val(x), query(t[i].left, l, mid, x));
        else return min(t[i].val(x), query(t[i].right, mid + 1, r, x));
    }

    void insert(T slope, T yIntercept) { insert(1, 0, n - 1, Line(slope, yIntercept)); }

    T query(T x) { return query(1, 0, n - 1, x); }
};

signed main() {
    FAST_IO;
#ifdef arujbansal_local
    setIO("input.txt", "output.txt");
#endif

    int n;
    cin >> n;

    int a[n + 1];
    for (int i = 1; i <= n; i++) cin >> a[i];

    LiChaoTree<int> cht;
    cht.init(N);

    vi dp(n + 1);
    dp[1] = a[1] * n;

    cht.insert(n, 0);

    int mx = a[1];

    for (int i = 2; i <= n; i++) {
        mx = max(mx, a[i]);
        cht.insert(n - i + 1, dp[i - 1]);
        dp[i] = cht.query(mx);
    }

    cout << dp[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