AhmedAshraff

Untitled

Jul 19th, 2024
31
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.09 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5. #define sz(s) (int)(s).size()
  6. #define all(s) s.begin(),s.end()
  7.  
  8. void Speed() {
  9. ios_base::sync_with_stdio(false);
  10. cin.tie(NULL);
  11. }
  12. const int N=1e5+5;
  13. ll dp[N/2];
  14. int vis[N/2];
  15. int v[N];
  16. vector<int>idx;
  17. int x,y;
  18. int n;
  19. int n2;
  20. int idd;
  21. ll rec(int i){
  22. if(i==n2)return 0;
  23. ll &ret=dp[i];
  24. if(vis[i]==idd)return ret;
  25. vis[i]=idd;
  26. ret=LLONG_MAX;
  27. ret=min(ret,rec(i+1)+1LL*(min(v[idx[i]-1],v[idx[i]+1])-v[idx[i]])*min(x,y));
  28. if(i+1<n2&&idx[i+1]-idx[i]==2){
  29. ret=min(ret,rec(i+2)+1LL*(v[idx[i]+1]-max(v[idx[i+1]],v[idx[i]]))*y+1LL*abs(v[idx[i+1]]-v[idx[i]])*min(x,y));
  30. }
  31. return ret;
  32. }
  33.  
  34. // 100000000 4 5 1 4
  35. void solve() {
  36. cin>>n>>x>>y;
  37. idx.clear();
  38. idd++;
  39. for(int i=0;i<n;i++)cin>>v[i];
  40. for (int i=1;i+1<n;i++){
  41. if(v[i]<v[i-1]&&v[i]<v[i+1])idx.push_back(i);
  42. }
  43. n2=idx.size();
  44. cout<<rec(0)<<'\n';
  45. }
  46.  
  47. int main() {
  48. Speed();
  49. int tc = 1;
  50. cin >> tc;
  51. while (tc--) {
  52. solve();
  53. }
  54. return 0;
  55. }
Advertisement
Add Comment
Please, Sign In to add comment