Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define int long long
- #define pb push_back
- #define all(x) x.begin(), x.end()
- using namespace std;
- const int N = 5e5 + 6;
- const double eps = 1e-7;
- const int INF = 1e9;
- int n, a[N], dp[N][2], c, r, del[N];
- pair<int, int> b[N];
- signed main() {
- ios_base::sync_with_stdio(0); cin.tie(0);
- cout.setf(ios::fixed); cout.precision(0);
- cin >> n >> c >> r;
- vector<int> possible;
- for (int i = 1; i <= n; i++) {
- cin >> a[i], b[i] = {abs(a[i]), i};
- possible.pb(abs(a[i]) + 1);
- }
- sort(all(possible));
- possible.resize(unique(all(possible)) - possible.begin());
- sort(b + 1, b + n + 1);
- int ans = 0;
- ///f = 0
- for (int i = 1; i <= n; i++) {
- dp[i][0] = dp[i - 1][0] + r;
- dp[i][1] = dp[i - 1][1] + r;
- if (a[i] < 0)
- dp[i][0] = min(dp[i][0], dp[i - 1][1]);
- if (a[i] > 0)
- dp[i][1] = min(dp[i][1], dp[i - 1][0]);
- }
- ans = min(dp[n][0], dp[n][1]);
- int cnt = 0;
- for (int i = 1; i + 1 <= n; i++) {
- if (a[i] > 0 && a[i + 1] > 0)
- cnt++;
- if (a[i] < 0 && a[i + 1] < 0)
- cnt++;
- }
- int cur = 1;
- del[0] = del[n + 1] = 1;
- for (auto f : possible) {
- while (cur <= n && abs(b[cur].first) < f) {
- int pos = b[cur].second;
- del[pos] = 1;
- if (!del[pos - 1]) {
- if (a[pos] > 0 && a[pos - 1] > 0)
- cnt--;
- if (a[pos] < 0 && a[pos - 1] < 0)
- cnt--;
- }
- if (!del[pos + 1]) {
- if (a[pos] > 0 && a[pos + 1] > 0)
- cnt--;
- if (a[pos] < 0 && a[pos + 1] < 0)
- cnt--;
- }
- cur++;
- }
- ans = min(ans, f * c + cnt * r);
- }
- cout << ans;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement