fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. typedef long long ll;
  6. typedef long double ld;
  7. constexpr int md = 1e9 + 7;
  8.  
  9. const int N = 50000003;
  10.  
  11. #define xi first
  12. #define yi second
  13. #define MAX 1000007
  14. #define INF 1e18
  15. #define SQ 500
  16.  
  17. ll gcd(ll a, ll b) {
  18.     while (b) a %= b, swap(a, b);
  19.     return a;
  20. }
  21. int x;
  22. struct SegTree{
  23.     int n;
  24.     vector<int> seg;
  25.     SegTree(int n) : n(n), seg(n * 2) {}
  26.     void build(vector<int>& arr) {
  27.         build(1, 0, n - 1, arr);
  28.     }
  29.     void upd(int pos, int val) {
  30.         upd(1, 0, n - 1, pos, val);
  31.     }
  32.     int query(int l, int r) {
  33.         return query(1, 0, n - 1, l, r);
  34.     }
  35.     void build(int idx, int l, int r, vector<int> &a) {
  36.         if (l == r) {
  37.             seg[idx] = a[l];
  38.             return;
  39.         }
  40.         int mid = (l + r) / 2;
  41.         build(idx + 1, l, mid, a);
  42.         build(idx + 2 * (mid - l + 1), mid + 1, r, a);
  43.         seg[idx] = min(seg[idx + 1], seg[idx + 2 * (mid - l + 1)]);
  44.     }
  45.     void upd(int idx, int l, int r, int pos, int val) {
  46.         if (l == r) {
  47.             seg[idx] = val;
  48.             return;
  49.         }
  50.         int mid = (l + r) / 2;
  51.         if (pos <= mid) upd(idx + 1, l, mid, pos, val);
  52.         else upd(idx + 2 * (mid - l + 1), mid + 1, r, pos, val);
  53.         seg[idx] = min(seg[idx + 1], seg[idx + 2 * (mid - l + 1)]);
  54.     }
  55.     int query(int idx, int tl, int tr, int l, int r) {
  56.         if (tl == tr) {
  57.             return tl;
  58.         }
  59.         int mid = (tl + tr) / 2, L = idx + 1, R = idx + 2 * (mid - tl + 1);
  60.         if (seg[L] <= x) return query(L, tl, mid, l, r);
  61.         if (seg[R] <= x) return query(R, mid + 1, tr, l, r);
  62.         return 1e9 + 1;
  63.     }
  64. };
  65. int main() {
  66.     ios::sync_with_stdio(false);
  67.     cin.tie(nullptr);
  68.     // freopen("boxes.in", "r", stdin);
  69.     int t;
  70.     cin >> t;
  71.     while (t--) {
  72.         int n, k, a , b; cin >> n >> k >> a >> b;
  73.         vector<int> arr(n);
  74.         vector<pair<int, int>> c(n);
  75.         --k;
  76.         for (int i = 0; i < n; i++) {
  77.             cin >> arr[i];
  78.             c[i] = {arr[i], i};
  79.         }
  80.         sort(c.begin(), c.end());
  81.         int v = arr[k];
  82.         vector<ll> suff(n + 1), suff2(n +1);
  83.         int beg = 0;
  84.         for (int i = n - 1; i >= 0; i--) {
  85.  
  86.             suff[i] = suff[i + 1] + (b + 2 * abs(k - c[i].second)) * (c[i].first - v);
  87.             suff2[i] = suff2[i + 1] + (b + 2 * abs(k - c[i].second));
  88.             if (c[i].first <= v) {
  89.                 beg = i;
  90.                 break;
  91.             }
  92.         }
  93.         ll ans = 1e18, sum = 0;
  94.         for (int i = beg; i < n; i++) {
  95.             sum = c[i].first - v;
  96.             ans = min(ans, suff[i] - (sum * suff2[i]) + sum * a);
  97.         }
  98.         cout << ans << endl;
  99.     }
  100.     return 0;
  101. }
  102.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FH6jNq
language:
C++14 (gcc 8.3)
created:
9 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!