Submission #320536

#	Time	Username	Problem	Language	Result	Execution time	Memory
320536		arujbansal	Discharging (NOI20_discharging)	C++17	100 / 100	146 ms	16172 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;

struct CHT {

    struct Line {
        int slope, yIntercept;

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

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

        int intersect(Line y) {
            return (y.yIntercept - yIntercept + slope - y.slope - 1) / (slope - y.slope);
        }
    };

    deque<pair<Line, int>> dq;

    void insert(int slope, int yIntercept) {
        Line newLine(slope, yIntercept);

        while (sz(dq) > 1 && dq.back().second >= dq.back().first.intersect(newLine))
            dq.pop_back();

        if (dq.empty()) {
            dq.emplace_back(newLine, 0);
            return;
        }

        dq.emplace_back(newLine, dq.back().first.intersect(newLine));
    }

    int query(int x) {

        while (sz(dq) > 1) {
            if (dq[1].second <= x) dq.pop_front();
            else break;
        }

        return dq[0].first.val(x);
    }

    int query2(int x) {
        auto qry = *lower_bound(dq.rbegin(), dq.rend(),
                                make_pair(Line(0, 0), x),
                                [&](const pair<Line, int> &a, const pair<Line, int> &b) {
                                    return a.second > b.second;
                                });

        return qry.first.val(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];

    CHT cht;

    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