Submission #584998

#	Time	Username	Problem	Language	Result	Execution time	Memory
584998		GioChkhaidze	Discharging (NOI20_discharging)	C++14	100 / 100	132 ms	16080 KiB

Discharging

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>

#define ll long long
#define f first
#define s second

using namespace std;

const int N = 1e6 + 5;

ll n, a[N], dp[N];
ll inf = 1e15;

struct Line {
	ll k;
	ll b;
	ll val(ll x) {
		return k *x + b;
	}
	pair < ll , ll > intr(Line yo) {
		ll one = yo.b - b;
		ll two = k - yo.k;
		if (two < 0) one *= -1, two *= -1;
		return {one, two};
	}
};

vector < Line > dq;
inline void upd(ll k, ll b) {
	Line lin = {k, b};
	while (dq.size() > 1) {
		Line lina = dq.end()[-1];
		Line linb = dq.end()[-2];
		pair < ll , ll > A = lin.intr(lina);
		pair < ll , ll > B = lina.intr(linb);
		if (A.f / A.s <= B.f / B.s) {
			dq.pop_back();
		}
			else break;
	}
	dq.push_back(lin);
}

ll get(ll x) {
	int l = 1, r = dq.size() - 1, mid, res = 0;
	while (l <= r) {
		mid = ((l + r) >> 1);
		if (dq[mid - 1].val(x) >= dq[mid].val(x)) {
			l = mid + 1, res = mid;
		}
			else {
			r = mid - 1;
		}
	}
	return dq[res].val(x);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		if (1 < i && a[i - 1] > a[i]) {
			a[i] = a[i - 1];
		}
	}

	dq.push_back({0, 0});
	for (int i = 1; i <= n; ++i) {
		/*
		dp[i] = inf;
		for (int j = i - 1; j >= 0; --j) {
			dp[i] = min(dp[i], dp[j] - j * a[i] + n * a[i]);
		} */
		dp[i] = get(a[i]) + n * a[i];
		upd(-i, dp[i]);
	}

	cout << dp[n] << "\n";
}
/*


dp[......]

dp[1..j]


.... j + 1 ... i   = max is a[i]

dp[i] = dp[j] + ( n - j ) * a[i]

dp[i] = dp[j] - j * a[i] + n * a[i];

Y = K * X + B

X = a[i]
K = -j;
B = dp[j];



*/

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