This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int a[N]; ll f[N];
struct Line {
ll A, B;
Line() : A(0), B(0) {}
Line (ll _a, ll _b) {
A = _a, B = _b;
}
};
struct ConvexHullTrick {
Line st[N]; int sz, it = 1;
long double G (Line x, Line y) {
return 1.0 * (x.B - y.B) / (y.A - x.A);
}
ll calc(Line x, ll v) {
return x.A * v + x.B;
}
void add(ll x, ll y) {
Line cur = Line(x, y);
if (sz && st[sz].A == x && st[sz].B <= y) return;
while (sz > 1 && G(cur, st[sz]) <= G(st[sz], st[sz - 1])) --sz;
st[++sz] = cur;
}
ll get(ll x) {
if (it > sz) it = sz;
while (it < sz && calc(st[it + 1], x) <= calc(st[it], x)) ++it;
return calc(st[it], x);
}
} cht;
signed main() {
cin.tie(0)->sync_with_stdio(0);
if (fopen("discharging.inp", "r")) {
freopen("discharging.inp", "r", stdin);
freopen("discharging.out", "w", stdout);
}
#ifdef LOCAL_MACHINE
if (fopen("task.inp", "r")) {
freopen("task.inp", "r", stdin);
freopen("task.out", "w", stdout);
}
#endif
int n; cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
cht.add(n, 0);
int mx = 0;
for (int i = 1; i <= n; ++i) {
mx = max(mx, a[i]);
f[i] = cht.get(mx);
cht.add(n - i, f[i]);
}
cout << f[n] << "\n";
}
Compilation message (stderr)
Discharging.cpp: In function 'int main()':
Discharging.cpp:45:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
45 | freopen("discharging.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Discharging.cpp:46:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
46 | freopen("discharging.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |