Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define int long long
- #define sz(a) ((int)((a).size()))
- #define fo(i,n) for(int i=0;i<n;i++)
- #define rfo(i,n) for(int i=n-1;i>=0;i--)
- #define fo1(i,n) for(int i=1;i<=n;i++)
- #define rfo1(i,n) for(int i=n;i>0;i--)
- #define pii pair<int,int>
- #define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
- #define all(v) v.begin(),v.end()
- #define vi vector<int>
- #define mii map<int,int>
- #define mivi map<int,vector<int>>
- #define tc int testcases;cin>>testcases;while(testcases--){solve();}
- #define setbits(x) __builtin_popcountll(x)
- #define zerobits(x) __builtin_ctzll(x)
- #define fill(x,y) memset(x,y,sizeof(x))
- #define f(i,container) for(auto &i:container)
- #define vs vector<string>
- #define pb push_back
- #define ff first
- #define ss second
- #define tcgoogle int testcases;cin>>testcases;fo1(t,testcases){cout << "Case #" << t << ": ";solve();}
- #define vvi vector<vector<int>>
- void file_io_()
- {
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- }
- void solve()
- {
- int n,rem,ins;
- cin>>n>>rem>>ins;
- vi v(n);
- fo(i,n) cin>>v[i];
- vi vv=v;
- int ans=0;
- if(*min_element(all(v))!=1){
- v.pb(1);
- ans+=ins;
- }
- int mx=*max_element(all(v));
- sort(all(v));
- int res=LLONG_MAX;
- res=min(res,ans+(rem*(sz(v)-1)));
- vi x=v;
- set<int>s;
- f(i,x) s.insert(i);
- v.clear();
- f(i,s) v.pb(i);
- mii m;
- f(i,x) m[i]++;
- int fixedrem=0;
- f(i,m) fixedrem+=(i.ss-1);
- fixedrem*=rem;
- res=min(res,fixedrem+ans+(ins*(mx-sz(m))));
- int sz=sz(v);
- for(int i:v){
- auto x=upper_bound(all(v),i);
- if((x-v.begin())==i){
- int o=x-v.begin();
- res=min(res,ans+fixedrem+(rem*(sz-o)));
- }
- else{
- int pp=x-v.begin();
- int toins=(i-pp)*ins;
- int torem=sz(v)-pp;
- toins*=ins;
- torem*=rem;
- res=min(res,ans+toins+torem+fixedrem);
- }
- }
- cout<<res<<"\n";
- }
- signed main()
- {
- file_io_();
- fast
- tc
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement