Advertisement
Guest User

Untitled

a guest
Mar 31st, 2023
252
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.54 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define sz(a) ((int)((a).size()))
  5. #define fo(i,n) for(int i=0;i<n;i++)
  6. #define rfo(i,n) for(int i=n-1;i>=0;i--)
  7. #define fo1(i,n) for(int i=1;i<=n;i++)
  8. #define rfo1(i,n) for(int i=n;i>0;i--)
  9. #define pii pair<int,int>
  10. #define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
  11. #define all(v) v.begin(),v.end()
  12. #define vi vector<int>
  13. #define mii map<int,int>
  14. #define mivi map<int,vector<int>>
  15. #define tc int testcases;cin>>testcases;while(testcases--){solve();}
  16. #define setbits(x) __builtin_popcountll(x)
  17. #define zerobits(x) __builtin_ctzll(x)
  18. #define fill(x,y) memset(x,y,sizeof(x))
  19. #define f(i,container) for(auto &i:container)
  20. #define vs vector<string>
  21. #define pb push_back
  22. #define ff first
  23. #define ss second
  24. #define tcgoogle int testcases;cin>>testcases;fo1(t,testcases){cout << "Case #" << t << ": ";solve();}
  25. #define vvi vector<vector<int>>
  26. void file_io_()
  27. {
  28. #ifndef ONLINE_JUDGE
  29. freopen("input.txt", "r", stdin);
  30. freopen("output.txt", "w", stdout);
  31. #endif
  32. }
  33. void solve()
  34. {
  35.  
  36. int n,rem,ins;
  37. cin>>n>>rem>>ins;
  38. vi v(n);
  39. fo(i,n) cin>>v[i];
  40. vi vv=v;
  41. int ans=0;
  42. if(*min_element(all(v))!=1){
  43. v.pb(1);
  44. ans+=ins;
  45. }
  46. int mx=*max_element(all(v));
  47.  
  48. sort(all(v));
  49. int res=LLONG_MAX;
  50. res=min(res,ans+(rem*(sz(v)-1)));
  51. vi x=v;
  52. set<int>s;
  53. f(i,x) s.insert(i);
  54. v.clear();
  55. f(i,s) v.pb(i);
  56. mii m;
  57. f(i,x) m[i]++;
  58.  
  59.  
  60. int fixedrem=0;
  61. f(i,m) fixedrem+=(i.ss-1);
  62.  
  63. fixedrem*=rem;
  64. res=min(res,fixedrem+ans+(ins*(mx-sz(m))));
  65.  
  66. int sz=sz(v);
  67. for(int i:v){
  68.  
  69. auto x=upper_bound(all(v),i);
  70.  
  71. if((x-v.begin())==i){
  72. int o=x-v.begin();
  73. res=min(res,ans+fixedrem+(rem*(sz-o)));
  74. }
  75. else{
  76. int pp=x-v.begin();
  77. int toins=(i-pp)*ins;
  78. int torem=sz(v)-pp;
  79. toins*=ins;
  80. torem*=rem;
  81. res=min(res,ans+toins+torem+fixedrem);
  82. }
  83. }
  84.  
  85. cout<<res<<"\n";
  86.  
  87.  
  88.  
  89. }
  90.  
  91.  
  92. signed main()
  93. {
  94. file_io_();
  95. fast
  96.  
  97.  
  98. tc
  99.  
  100.  
  101. return 0;
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement