#include <bits/stdc++.h>
#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define all(v) (v).begin(), (v).end()
#define F first
#define S second
#define __builtin_popcount __builtin_popcountll
#define sz(v) ((int) (v).size())
#define uni(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define pii(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
///
const int mod = 1e9 + 7;
const int INF = 1e9 + 7;
const ll oo = 1e18 + 7;
const int N = 1e6 + 5;
int n, a[N], nxt[N];
ll dp[N];
struct line
{
ll a, b;
line (const ll &_a = 0, const ll &_b = 0)
{
a = _a;
b = _b;
}
ll eval(const ll &x)
{
return a * x + b;
}
};
deque <line> st;
bool bad(const line &l1, const line &l2, const line &l3)
{
return long double (l3.b - l1.b) * (l1.a - l2.a) < long double (l2.b - l1.b) * (l1.a - l3.a);
}
void add(const line &x)
{
while (st.size() >= 2 && bad(st[st.size() - 2], st[st.size() - 1], x)) st.pop_back();
st.push_back(x);
}
ll query(ll x)
{
while (st.size() >= 2 && st[0].eval(x) >= st[1].eval(x)) st.pop_front();
return st[0].eval(x);
}
void Input()
{
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
nxt[1] = 1;
for (int i = 2; i <= n; i ++)
if (a[nxt[i - 1]] < a[i]) nxt[i] = i;
else nxt[i] = nxt[i - 1];
}
void solve()
{
add(line(0, 0));
for (int i = 1; i <= n; i ++)
{
dp[i] = query(a[nxt[i]]) + 1LL * n * a[nxt[i]];
add(line(-i, dp[i]));
}
cout << dp[n];
}
int main()
{
std::ios_base::sync_with_stdio(0); cin.tie(0);
// freopen("DIAMOND.inp", "r", stdin);
// freopen("DIAMOND.out", "w", stdout);
int test = 1;
//cin >> test;
while (test--)
{
Input();
solve();
}
return 0;
}
Compilation message
Discharging.cpp: In function 'bool bad(const line&, const line&, const line&)':
Discharging.cpp:45:12: error: expected primary-expression before 'long'
45 | return long double (l3.b - l1.b) * (l1.a - l2.a) < long double (l2.b - l1.b) * (l1.a - l3.a);
| ^~~~
Discharging.cpp:45:11: error: expected ';' before 'long'
45 | return long double (l3.b - l1.b) * (l1.a - l2.a) < long double (l2.b - l1.b) * (l1.a - l3.a);
| ^~~~~
| ;
Discharging.cpp:45:12: error: expected primary-expression before 'long'
45 | return long double (l3.b - l1.b) * (l1.a - l2.a) < long double (l2.b - l1.b) * (l1.a - l3.a);
| ^~~~
