Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <iostream>
- #include <algorithm>
- #include <cstdlib>
- #include <cstring>
- #include <string>
- #include <vector>
- #include <map>
- #include <set>
- #include <cmath>
- #include <ctime>
- #include <cassert>
- using namespace std;
- #define pb push_back
- #define mp make_pair
- #define sz(A) (int)(A).size()
- typedef long long LL;
- typedef long double LD;
- const int N = 1e5 + 10;
- const int SZ = 4 * N;
- const LL INF = (LL) 1e18;
- int n, u, v, a[N];
- LL t[SZ], topush[SZ], delta[N];
- void addVal (int v, int val)
- {
- topush[v] += val;
- t[v] += val;
- }
- void push (int v)
- {
- addVal(v * 2 + 1, topush[v]);
- addVal(v * 2 + 2, topush[v]);
- topush[v] = 0;
- }
- void build (int v, int l, int r)
- {
- //cerr << v << ' ' << l << ' ' << r << endl;
- if (l + 1 == r) {
- if (l == 0)
- t[v] = delta[l];
- else
- t[v] = INF;
- return;
- }
- int m = (l + r) / 2;
- build(v * 2 + 1, l, m);
- build(v * 2 + 2, m, r);
- t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
- }
- void add (int v, int l, int r, int L, int R, int val)
- {
- if (L <= l && r <= R) {
- addVal(v, val);
- return;
- }
- if (r <= L || R <= l)
- return;
- push(v);
- int m = (l + r) / 2;
- add(v * 2 + 1, l, m, L, R, val);
- add(v * 2 + 2, m, r, L, R, val);
- t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
- }
- LL get (int v, int l, int r, int L, int R)
- {
- if (L <= l && r <= R)
- return t[v];
- if (r <= L || R <= l)
- return INF;
- push(v);
- int m = (l + r) / 2;
- return min(get(v * 2 + 1, l, m, L, R), get(v * 2 + 2, m, r, L, R));
- }
- void update (int v, int l, int r, int pos, LL val)
- {
- if (l + 1 == r) {
- t[v] = min(t[v], val);
- return;
- }
- push(v);
- int m = (l + r) / 2;
- if (pos < m)
- update(v * 2 + 1, l, m, pos, val);
- else
- update(v * 2 + 2, m, r, pos, val);
- t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
- }
- int main()
- {
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- scanf("%d%d%d", &n, &u, &v);
- for (int i = N - 3; i >= 0; i--) {
- delta[i] = delta[i + 1] + v;
- }
- for (int i = 0; i < n; i++) {
- scanf("%d", a + i);
- }
- build(0, 0, N);
- LL ans = n * u;
- for (int i = 0; i < n; i++) {
- LL cur_res = get(0, 0, N, 0, a[i]) - delta[a[i] - 1];
- LL global = cur_res + u * (n - i - 1);
- ans = min(ans, global);
- add(0, 0, N, 0, N, u);
- update(0, 0, N, a[i], cur_res + delta[a[i]]);
- }
- cout << ans << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement