oj.uz

Submission #1037031

# Submission time Handle Problem Language Result Execution time Memory
1037031 2024-07-27T22:34:08 Z model_code Tricks of the Trade (CEOI23_trade) C++17
50 / 100
 2115 ms 38380 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 KB Partially correct
2 Partially correct 0 ms 348 KB Partially correct

Subtask #1
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Partially correct
2 Partially correct 1 ms 348 KB Partially correct
3 Partially correct 0 ms 344 KB Partially correct
4 Partially correct 0 ms 348 KB Partially correct
5 Partially correct 1 ms 348 KB Partially correct
6 Partially correct 1 ms 348 KB Partially correct
7 Partially correct 1 ms 348 KB Partially correct
8 Partially correct 1 ms 348 KB Partially correct
9 Partially correct 0 ms 348 KB Partially correct
10 Partially correct 1 ms 348 KB Partially correct
11 Partially correct 1 ms 348 KB Partially correct

Subtask #2
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Partially correct
2 Partially correct 1 ms 348 KB Partially correct
3 Partially correct 0 ms 344 KB Partially correct
4 Partially correct 0 ms 348 KB Partially correct
5 Partially correct 1 ms 348 KB Partially correct
6 Partially correct 1 ms 348 KB Partially correct
7 Partially correct 1 ms 348 KB Partially correct
8 Partially correct 1 ms 348 KB Partially correct
9 Partially correct 0 ms 348 KB Partially correct
10 Partially correct 1 ms 348 KB Partially correct
11 Partially correct 1 ms 348 KB Partially correct
12 Partially correct 0 ms 348 KB Partially correct
13 Partially correct 0 ms 348 KB Partially correct
14 Partially correct 0 ms 348 KB Partially correct
15 Partially correct 1 ms 600 KB Partially correct
16 Partially correct 0 ms 348 KB Partially correct
17 Partially correct 0 ms 348 KB Partially correct
18 Partially correct 1 ms 348 KB Partially correct
19 Partially correct 1 ms 348 KB Partially correct
20 Partially correct 0 ms 348 KB Partially correct
21 Partially correct 1 ms 348 KB Partially correct
22 Partially correct 1 ms 348 KB Partially correct
23 Partially correct 3 ms 1116 KB Partially correct
24 Partially correct 13 ms 988 KB Partially correct
25 Partially correct 23 ms 1116 KB Partially correct
26 Partially correct 22 ms 1108 KB Partially correct
27 Partially correct 15 ms 1116 KB Partially correct
28 Partially correct 9 ms 860 KB Partially correct
29 Partially correct 12 ms 1116 KB Partially correct

Subtask #3
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB Partially correct
2 Partially correct 452 ms 24988 KB Partially correct
3 Partially correct 629 ms 22940 KB Partially correct
4 Partially correct 761 ms 28952 KB Partially correct
5 Partially correct 800 ms 24536 KB Partially correct
6 Partially correct 742 ms 22948 KB Partially correct
7 Partially correct 1855 ms 29448 KB Partially correct
8 Partially correct 831 ms 26012 KB Partially correct
9 Partially correct 641 ms 23196 KB Partially correct
10 Partially correct 699 ms 23116 KB Partially correct

Subtask #4
10.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB Partially correct
2 Partially correct 452 ms 24988 KB Partially correct
3 Partially correct 629 ms 22940 KB Partially correct
4 Partially correct 761 ms 28952 KB Partially correct
5 Partially correct 800 ms 24536 KB Partially correct
6 Partially correct 742 ms 22948 KB Partially correct
7 Partially correct 1855 ms 29448 KB Partially correct
8 Partially correct 831 ms 26012 KB Partially correct
9 Partially correct 641 ms 23196 KB Partially correct
10 Partially correct 699 ms 23116 KB Partially correct
11 Partially correct 0 ms 348 KB Partially correct
12 Partially correct 430 ms 24928 KB Partially correct
13 Partially correct 619 ms 23120 KB Partially correct
14 Partially correct 818 ms 29012 KB Partially correct
15 Partially correct 819 ms 24656 KB Partially correct
16 Partially correct 745 ms 23132 KB Partially correct
17 Partially correct 1905 ms 29652 KB Partially correct
18 Partially correct 773 ms 25952 KB Partially correct
19 Partially correct 612 ms 23152 KB Partially correct
20 Partially correct 657 ms 23116 KB Partially correct
21 Partially correct 0 ms 348 KB Partially correct
22 Partially correct 0 ms 348 KB Partially correct
23 Partially correct 1 ms 348 KB Partially correct
24 Partially correct 1 ms 348 KB Partially correct
25 Partially correct 1 ms 348 KB Partially correct
26 Partially correct 1 ms 348 KB Partially correct
27 Partially correct 1 ms 348 KB Partially correct
28 Partially correct 0 ms 348 KB Partially correct
29 Partially correct 1 ms 348 KB Partially correct
30 Partially correct 0 ms 348 KB Partially correct
31 Partially correct 970 ms 28320 KB Partially correct
32 Partially correct 812 ms 23136 KB Partially correct
33 Partially correct 1440 ms 30304 KB Partially correct
34 Partially correct 1390 ms 22940 KB Partially correct
35 Partially correct 1261 ms 22948 KB Partially correct
36 Partially correct 2115 ms 29012 KB Partially correct
37 Partially correct 793 ms 23184 KB Partially correct

Subtask #5
25.0 / 45.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 KB Partially correct
2 Partially correct 0 ms 348 KB Partially correct
3 Partially correct 0 ms 348 KB Partially correct
4 Partially correct 1 ms 348 KB Partially correct
5 Partially correct 0 ms 344 KB Partially correct
6 Partially correct 0 ms 348 KB Partially correct
7 Partially correct 1 ms 348 KB Partially correct
8 Partially correct 1 ms 348 KB Partially correct
9 Partially correct 1 ms 348 KB Partially correct
10 Partially correct 1 ms 348 KB Partially correct
11 Partially correct 0 ms 348 KB Partially correct
12 Partially correct 1 ms 348 KB Partially correct
13 Partially correct 1 ms 348 KB Partially correct
14 Partially correct 0 ms 348 KB Partially correct
15 Partially correct 0 ms 348 KB Partially correct
16 Partially correct 0 ms 348 KB Partially correct
17 Partially correct 1 ms 600 KB Partially correct
18 Partially correct 0 ms 348 KB Partially correct
19 Partially correct 0 ms 348 KB Partially correct
20 Partially correct 1 ms 348 KB Partially correct
21 Partially correct 1 ms 348 KB Partially correct
22 Partially correct 0 ms 348 KB Partially correct
23 Partially correct 1 ms 348 KB Partially correct
24 Partially correct 1 ms 348 KB Partially correct
25 Partially correct 3 ms 1116 KB Partially correct
26 Partially correct 13 ms 988 KB Partially correct
27 Partially correct 23 ms 1116 KB Partially correct
28 Partially correct 22 ms 1108 KB Partially correct
29 Partially correct 15 ms 1116 KB Partially correct
30 Partially correct 9 ms 860 KB Partially correct
31 Partially correct 12 ms 1116 KB Partially correct
32 Partially correct 1 ms 348 KB Partially correct
33 Partially correct 452 ms 24988 KB Partially correct
34 Partially correct 629 ms 22940 KB Partially correct
35 Partially correct 761 ms 28952 KB Partially correct
36 Partially correct 800 ms 24536 KB Partially correct
37 Partially correct 742 ms 22948 KB Partially correct
38 Partially correct 1855 ms 29448 KB Partially correct
39 Partially correct 831 ms 26012 KB Partially correct
40 Partially correct 641 ms 23196 KB Partially correct
41 Partially correct 699 ms 23116 KB Partially correct
42 Partially correct 0 ms 348 KB Partially correct
43 Partially correct 430 ms 24928 KB Partially correct
44 Partially correct 619 ms 23120 KB Partially correct
45 Partially correct 818 ms 29012 KB Partially correct
46 Partially correct 819 ms 24656 KB Partially correct
47 Partially correct 745 ms 23132 KB Partially correct
48 Partially correct 1905 ms 29652 KB Partially correct
49 Partially correct 773 ms 25952 KB Partially correct
50 Partially correct 612 ms 23152 KB Partially correct
51 Partially correct 657 ms 23116 KB Partially correct
52 Partially correct 0 ms 348 KB Partially correct
53 Partially correct 0 ms 348 KB Partially correct
54 Partially correct 1 ms 348 KB Partially correct
55 Partially correct 1 ms 348 KB Partially correct
56 Partially correct 1 ms 348 KB Partially correct
57 Partially correct 1 ms 348 KB Partially correct
58 Partially correct 1 ms 348 KB Partially correct
59 Partially correct 0 ms 348 KB Partially correct
60 Partially correct 1 ms 348 KB Partially correct
61 Partially correct 0 ms 348 KB Partially correct
62 Partially correct 970 ms 28320 KB Partially correct
63 Partially correct 812 ms 23136 KB Partially correct
64 Partially correct 1440 ms 30304 KB Partially correct
65 Partially correct 1390 ms 22940 KB Partially correct
66 Partially correct 1261 ms 22948 KB Partially correct
67 Partially correct 2115 ms 29012 KB Partially correct
68 Partially correct 793 ms 23184 KB Partially correct
69 Partially correct 1 ms 348 KB Partially correct
70 Partially correct 437 ms 24916 KB Partially correct
71 Partially correct 618 ms 22940 KB Partially correct
72 Partially correct 833 ms 28816 KB Partially correct
73 Partially correct 808 ms 24472 KB Partially correct
74 Partially correct 771 ms 23120 KB Partially correct
75 Partially correct 2043 ms 29584 KB Partially correct
76 Partially correct 727 ms 26016 KB Partially correct
77 Partially correct 534 ms 23136 KB Partially correct
78 Partially correct 673 ms 23120 KB Partially correct
79 Partially correct 0 ms 348 KB Partially correct
80 Partially correct 0 ms 348 KB Partially correct
81 Partially correct 1 ms 348 KB Partially correct
82 Partially correct 0 ms 348 KB Partially correct
83 Partially correct 0 ms 348 KB Partially correct
84 Partially correct 1 ms 348 KB Partially correct
85 Partially correct 0 ms 348 KB Partially correct
86 Partially correct 0 ms 348 KB Partially correct
87 Partially correct 1 ms 348 KB Partially correct
88 Partially correct 1 ms 348 KB Partially correct
89 Partially correct 1078 ms 28316 KB Partially correct
90 Partially correct 831 ms 23116 KB Partially correct
91 Partially correct 1385 ms 30256 KB Partially correct
92 Partially correct 1365 ms 22944 KB Partially correct
93 Partially correct 1200 ms 22948 KB Partially correct
94 Partially correct 1813 ms 28864 KB Partially correct
95 Partially correct 765 ms 23376 KB Partially correct
96 Partially correct 3 ms 1116 KB Partially correct
97 Partially correct 14 ms 988 KB Partially correct
98 Partially correct 22 ms 1068 KB Partially correct
99 Partially correct 30 ms 1004 KB Partially correct
100 Partially correct 19 ms 1116 KB Partially correct
101 Partially correct 9 ms 860 KB Partially correct
102 Partially correct 19 ms 1060 KB Partially correct
103 Partially correct 1682 ms 28948 KB Partially correct
104 Partially correct 1303 ms 23088 KB Partially correct
105 Partially correct 1362 ms 22952 KB Partially correct
106 Partially correct 1899 ms 25440 KB Partially correct
107 Partially correct 190 ms 29008 KB Partially correct
108 Partially correct 1771 ms 29900 KB Partially correct
109 Partially correct 861 ms 38380 KB Partially correct
110 Partially correct 1303 ms 32948 KB Partially correct
111 Partially correct 459 ms 25872 KB Partially correct
112 Partially correct 1247 ms 28868 KB Partially correct