Advertisement
MaxObznyi

Untitled

Feb 16th, 2021
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.89 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. #define pb push_back
  4. #define all(x) x.begin(), x.end()
  5. using namespace std;
  6.  
  7. const int N = 5e5 + 6;
  8. const double eps = 1e-7;
  9. const int INF = 1e9;
  10.  
  11. int n, a[N], dp[N][2], c, r, del[N];
  12. pair<int, int> b[N];
  13.  
  14. signed main() {
  15. ios_base::sync_with_stdio(0); cin.tie(0);
  16. cout.setf(ios::fixed); cout.precision(0);
  17. cin >> n >> c >> r;
  18. vector<int> possible;
  19. for (int i = 1; i <= n; i++) {
  20. cin >> a[i], b[i] = {abs(a[i]), i};
  21. possible.pb(abs(a[i]) + 1);
  22. }
  23. sort(all(possible));
  24. possible.resize(unique(all(possible)) - possible.begin());
  25.  
  26. sort(b + 1, b + n + 1);
  27.  
  28. int ans = 0;
  29. ///f = 0
  30. for (int i = 1; i <= n; i++) {
  31. dp[i][0] = dp[i - 1][0] + r;
  32. dp[i][1] = dp[i - 1][1] + r;
  33.  
  34. if (a[i] < 0)
  35. dp[i][0] = min(dp[i][0], dp[i - 1][1]);
  36.  
  37. if (a[i] > 0)
  38. dp[i][1] = min(dp[i][1], dp[i - 1][0]);
  39. }
  40. ans = min(dp[n][0], dp[n][1]);
  41.  
  42. int cnt = 0;
  43. for (int i = 1; i + 1 <= n; i++) {
  44. if (a[i] > 0 && a[i + 1] > 0)
  45. cnt++;
  46. if (a[i] < 0 && a[i + 1] < 0)
  47. cnt++;
  48. }
  49.  
  50. int cur = 1;
  51. del[0] = del[n + 1] = 1;
  52. for (auto f : possible) {
  53. while (cur <= n && abs(b[cur].first) < f) {
  54. int pos = b[cur].second;
  55. del[pos] = 1;
  56. if (!del[pos - 1]) {
  57. if (a[pos] > 0 && a[pos - 1] > 0)
  58. cnt--;
  59. if (a[pos] < 0 && a[pos - 1] < 0)
  60. cnt--;
  61. }
  62.  
  63. if (!del[pos + 1]) {
  64. if (a[pos] > 0 && a[pos + 1] > 0)
  65. cnt--;
  66. if (a[pos] < 0 && a[pos + 1] < 0)
  67. cnt--;
  68. }
  69. cur++;
  70. }
  71. ans = min(ans, f * c + cnt * r);
  72. }
  73. cout << ans;
  74. return 0;
  75. }
  76.  
  77.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement