Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- #define sz(s) (int)(s).size()
- #define all(s) s.begin(),s.end()
- void Speed() {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- }
- const int N=1e5+5;
- ll dp[N/2];
- int vis[N/2];
- int v[N];
- vector<int>idx;
- int x,y;
- int n;
- int n2;
- int idd;
- ll rec(int i){
- if(i==n2)return 0;
- ll &ret=dp[i];
- if(vis[i]==idd)return ret;
- vis[i]=idd;
- ret=LLONG_MAX;
- ret=min(ret,rec(i+1)+1LL*(min(v[idx[i]-1],v[idx[i]+1])-v[idx[i]])*min(x,y));
- if(i+1<n2&&idx[i+1]-idx[i]==2){
- 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));
- }
- return ret;
- }
- // 100000000 4 5 1 4
- void solve() {
- cin>>n>>x>>y;
- idx.clear();
- idd++;
- for(int i=0;i<n;i++)cin>>v[i];
- for (int i=1;i+1<n;i++){
- if(v[i]<v[i-1]&&v[i]<v[i+1])idx.push_back(i);
- }
- n2=idx.size();
- cout<<rec(0)<<'\n';
- }
- int main() {
- Speed();
- int tc = 1;
- cin >> tc;
- while (tc--) {
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment