WA on 52 求调 TAT
查看原帖
WA on 52 求调 TAT
526017
COsm0s楼主2025/6/13 19:02
#include <bits/stdc++.h>
using namespace std;
using db = double;
using lb = long double;
using ull = unsigned long long;
using uint = unsigned int;
using ll = long long;
// using i128 = __int128;
// using ui128 = unsigned __int128;
#define REP(i, first, last) for (int i = (int)(first); i <= (int)(last); ++i)
#define DOW(i, first, last) for (int i = (int)(first); i >= (int)(last); --i)
#define int long long
#define pb emplace_back
#define ob pop_back
#define pii pair<int, int>
#define MPR make_pair
#define fi first
#define se second
#define tpl tuple<int, int, int>
#define MTP make_tuple
#define poly vector<int>
#define polyp vector<pii>
#define polyt vector<tpl>
#define all(x) x.begin(), x.end()
#define CVR(a, q) memset(a, q, sizeof a)
#define CLR(a) memset(a, 0, sizeof a)
#define CPY(a, q) memcpy(a, q, sizeof a)
#define PCT __builtin_popcount
const int N = 2e5 + 5, M = 1e6 + 5;
const int mod1 = 1e9 + 7, mod2 = 998244353, mod = 1e9 + 7;
const long long inf = 1e18;
const int dx[] = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
const int dy[] = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int n, m, k, val[N], k1, k2, pre[N];
poly a, b, c, d;
int sa[N], sb[N], sc[N];
bitset<N> w1, w2, w;
unordered_map<int, int> mp;
int idx;
int id(int x) {
  if(!mp.count(x)) return mp[x] = ++ idx;
  return mp[x];
}
struct node {
  int siz, sum;
} t[N << 2];
void pushup(int u) {
  t[u].siz = t[u << 1].siz + t[u << 1 | 1].siz;
  t[u].sum = t[u << 1].sum + t[u << 1 | 1].sum;
}
void upd(int u, int l, int r, int p, int d) {
  if(l == r) return t[u].siz += d, t[u].sum += pre[l] * d, void();
  int mid = l + r >> 1;
  if(p <= mid) upd(u << 1, l, mid, p, d);
  else upd(u << 1 | 1, mid + 1, r, p, d);
  pushup(u);
}
int qry(int u, int l, int r, int d) {
  // cerr << l << ' ' << r << ' ' << d << '\n';
  if(!d) return 0;
  if(l == r) return t[u].sum;
  int mid = l + r >> 1;
  if(t[u << 1].siz >= d) return qry(u << 1, l, mid, d);
  return t[u << 1].sum + qry(u << 1 | 1, mid + 1, r, d - t[u << 1].siz);
}
void Solve() {
  cin >> n >> m >> k;
  REP(i, 1, n) cin >> val[i];
  cin >> k1;
  REP(i, 1, k1) {
    int x; cin >> x;
    w1[x] = 1;
  }
  cin >> k2;
  REP(i, 1, k2) {
    int x; cin >> x;
    w2[x] = 1;
  }
  w = w1 & w2;
  REP(i, 1, n) if(w1[i] && !w[i]) a.pb(val[i]);
  REP(i, 1, n) if(w2[i] && !w[i]) b.pb(val[i]);
  REP(i, 1, n) if(w[i]) c.pb(val[i]);
  REP(i, 1, n) if(!w1[i] && !w2[i]) d.pb(val[i]);
  sort(all(a)), sort(all(b));
  sort(all(c)), sort(all(d));
  sort(val + 1, val + n + 1);
  REP(i, 1, n) pre[id(val[i])] = val[i];
  REP(i, 1, a.size()) sa[i] = sa[i - 1] + a[i - 1];
  REP(i, 1, b.size()) sb[i] = sb[i - 1] + b[i - 1];
  REP(i, 1, c.size()) sc[i] = sc[i - 1] + c[i - 1], upd(1, 1, idx, id(c[i - 1]), 1);
  REP(i, k + 1, a.size()) upd(1, 1, idx, id(a[i - 1]), 1);
  REP(i, k + 1, b.size()) upd(1, 1, idx, id(b[i - 1]), 1);
  REP(i, 1, d.size()) upd(1, 1, idx, id(d[i - 1]), 1);
  int p = min((int)a.size(), k), q = min((int)b.size(), k), ans = inf;
  REP(i, 0, min((int)c.size(), k)) {
    while(p && p > k - i) upd(1, 1, idx, id(a[p - 1]), 1), p --;
    while(q && q > k - i) upd(1, 1, idx, id(b[q - 1]), 1), q --;
    if(i) upd(1, 1, idx, id(c[i - 1]), -1);
    int po = m - i - p - q;
    if(po > t[1].siz || po < 0 || p < k - i || q < k - i) continue;
    int tval = sc[i] + sa[p] + sb[q] + qry(1, 1, idx, po);
    // if(tval == 20) cerr << i << ' ' << k - i << ' ' << sc[i] << ' ' << sa[k - i] << ' ' << sb[k - i] << ' ' << po << ' ' << t[1].siz << ' ' << t[1].sum << ' ' << p << ' ' << q << '\n';
    ans = min(ans, tval);
  }
  if(ans == inf) cout << -1 << '\n';
  else cout << ans << '\n';
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  int T = 1;
  // cin >> T;
  while (T--) {
    Solve();
  }
  return 0;
}
2025/6/13 19:02
加载中...