#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define ld long double
#define pii pair<int,int>
#define pll pair<ll, ll>
#define sz(x) int(x.size())
using namespace std;
const int maxn = 100100;
const ll inf = 1e18;
ll n, q, arr[maxn];
class node {
public:
ll val;
ll ind;
}tree[4*maxn];
node leaf_value(ll val, ll ind) {
return {val, ind};
}
node merge_values(node a, node b) {
node c;
if(a.val > b.val)
c = a;
else if(a.val < b.val)
c = b;
else {
c.val = a.val;
c.ind = min(a.ind, b.ind);
}
return c;
}
void build(int li=0, int ri=n-1, int index=1) {
if(li == ri) {
tree[index] = leaf_value(arr[li], li);
}
else {
int mid = (li + ri) / 2;
build(li, mid, 2*index);
build(mid+1, ri, 2*index+1);
tree[index] = merge_values(tree[2*index], tree[2*index+1]);
}
}
node empty_node;
node query(int ql, int qr, int li=0, int ri=n-1, int index=1) {
if(li > qr || ri < ql) return empty_node;
else if(li >= ql && ri <= qr) return tree[index];
else {
int mid = (li + ri) / 2;
return merge_values(query(ql, qr, li, mid, 2*index), query(ql, qr, mid+1, ri, 2*index+1));
}
}
struct cht {
struct line {
ll k, b; ld x;
ll val; bool isquery;
line(ll _k = 0, ll _b = 0) :
k(_k), b(_b), x(-inf), val(0), isquery(false) {}
ll eval(ll x) const { return k * x + b; }
bool parallel(const line& l) const {return k == l.k; }
ld intersection(const line& l) const {
if(parallel(l)) return inf;
return (1.0*l.b - b) / (1.0 * k - l.k);
}
bool operator <(const line& l) const {
if(l.isquery) return x < l.val;
else return k < l.k;
}
};
set<line> hull;
typedef set<line>::iterator iter;
bool cPrev(iter it) { return it != hull.begin(); }
bool cNext(iter it) { return it != hull.end() && next(it) != hull.end(); }
bool bad(const line &l1, const line &l2, const line &l3) {
return l1.intersection(l3) <= l1.intersection(l2);
}
bool bad(iter it) {
return cPrev(it) && cNext(it) && bad(*prev(it), *it, *next(it));
}
iter update(iter it) {
if(!cPrev(it)) return it;
ld x = it -> intersection(*prev(it));
line tmp(*it); tmp.x = x;
it = hull.erase(it);
return hull.insert(it, tmp);
}
void addLine(ll k, ll b) {
line l(k, b);
iter it = hull.lower_bound(l);
if(it != hull.end() && l.parallel(*it)) {
if(it->b < b) it = hull.erase(it);
else return;
}
it = hull.insert(it, l);
if(bad(it)) return (void) hull.erase(it);
while(cPrev(it) && bad(prev(it))) hull.erase(prev(it));
while(cNext(it) && bad(next(it))) hull.erase(next(it));
it = update(it);
if(cPrev(it)) update(prev(it));
if(cNext(it)) update(next(it));
}
ll query(ll x) {
if(hull.empty()) return -inf;
line tmp;
tmp.val = x; tmp.isquery = true;
iter it = --hull.lower_bound(tmp);
return it->eval(x);
}
}ds;
ll pref[maxn];
ll dp[maxn];
int main() {
cin>>n;
empty_node = {INT_MIN, -1};
for(int i=0;i<n;i++) {
cin>>arr[i];
}
build();
int curr = n - 1;
ll result = 0LL;
vector<pll> values;
while(curr >= 0) {
node curr_query = query(0, curr);
values.pb(mp(curr_query.val, curr - curr_query.ind + 1));
curr = curr_query.ind - 1;
}
values.pb(mp(0, 0));
reverse(values.begin(), values.end());
for(int i=1;i<sz(values);i++) {
pref[i] = pref[i-1] + values[i].second;
dp[i] = dp[i-1] + (n - pref[i-1]) * values[i].first;
if(ds.hull.size() > 0) dp[i] = min(dp[i], values[i].first*(n) + ds.query(-values[i].first));
ds.addLine(pref[i-1], dp[i-1]);
}
cout<<dp[sz(values) - 1]<<"\n";
return 0;
}
Compilation message
Discharging.cpp: In function 'int main()':
Discharging.cpp:153:5: warning: unused variable 'result' [-Wunused-variable]
153 | ll result = 0LL;
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
91 ms |
3064 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
