Submission #1037030

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037030		model_code	Tricks of the Trade (CEOI23_trade)	C++17	100 / 100	2097 ms	38372 KiB

trade

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define sz(x) ((int) (x).size())

const ll inf = 1LL << 60;

struct divide_and_conquer_optimization {
  int N, K, p[2] = {0, 0};
  ll s = 0, mdp = -inf;
  vector<int> &A, &B, omax;
  vector<ll> dp;
  multiset<int> h, l;
  vector<vector<int>> sv, ev;
  void addToSet(int v) {
    if (l.empty() || v >= *h.begin()) {
      h.insert(v), s += v;
      if (sz(h) > K)
        l.insert(v = *h.begin()), h.erase(h.begin()), s -= v;
    } else
      l.insert(v);
  }
  void removeFromSet(int v) {
    if (l.empty() || v >= *h.begin()) {
      h.erase(h.find(v)), s -= v;
      if (sz(h) < K && !l.empty())
        h.insert(v = *(--l.end())), s += v, l.erase(--l.end());
    } else
      l.erase(l.find(v));
  }
  ll compute(int i, int j) {
    while (p[0] > j)
      addToSet(A[--p[0]]), s -= B[p[0]];
    while (p[1] < i + 1)
      addToSet(A[p[1]]), s -= B[p[1]++];
    while (p[0] < j)
      removeFromSet(A[p[0]]), s += B[p[0]++];
    while (p[1] > i + 1)
      removeFromSet(A[--p[1]]), s += B[p[1]];
    return s;
  }
  divide_and_conquer_optimization(int N, int K, vector<int> & A, vector<int> & B) : N(N), K(K), A(A), B(B), omax(N), dp(N, -inf), sv(N), ev(N) {
    solvemax(K - 1, N, 0, N);
    int lomax = 0;
    for (int i = 0; i < N; i++) {
      if (dp[i] != mdp)
        continue;
      for (int j = lomax; j <= omax[i]; j++) {
        ll v = compute(i, j);
        if (v == mdp)
          sv[j].push_back(*h.begin()), ev[i].push_back(*h.begin());
      }
      lomax = omax[i];
    }
  }
  void solvemax(int l, int r, int lo, int ro) {
    if (l >= r)
      return;
    int m = (l + r) / 2;
    for (int i = lo; i < min(ro, m - K + 2); i++) {
      ll v = compute(m, i);
      if (v >= dp[m])
        dp[m] = v, omax[m] = i, mdp = max(mdp, v);
    }
    solvemax(m + 1, r, omax[m], ro);
    solvemax(l, m, lo, omax[m] + 1);
  }
};

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> A(N), B(N);
  for (int i = 0; i < N; i++)
    cin >> B[i];
  for (int i = 0; i < N; i++)
    cin >> A[i];
  divide_and_conquer_optimization dcf(N, K, A, B);
  cout << dcf.mdp << "\n";
  multiset<int> v;
  for (int i = 0; i < N; i++) {
    for (int u : dcf.sv[i])
      v.insert(u);
    cout << (!v.empty() && *v.begin() <= A[i]);
    for (int u : dcf.ev[i])
      v.erase(v.find(u));
  }
  cout << "\n";
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 45 / 45