답안 #1073012

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1073012	2024-08-24T08:35:50 Z	NeroZein	Tricks of the Trade (CEOI23_trade)	C++17	100 / 100	3724 ms	45544 KB

trade

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

const int N = 250003;

int n, k;
int g[N];
int lx[N];
int cl, cr;
bool ok[N];
int pre[N];
long long s2; 
int c[N], s[N];
long long dp[N];
long long pref[N]; 
multiset<int> se, se2;
vector<int> to_add[N], to_rem[N];

void balance() {
  if ((int) se2.size() > k) {
    int mn = *se2.begin();
    s2 -= mn;
    se.insert(mn); 
    se2.erase(se2.begin());
  }
  if ((int) se2.size() < k && !se.empty()) {
    int mx = *se.rbegin();
    s2 += mx; 
    se2.insert(mx); 
    se.erase(se.find(mx));
  }
}

void add(int ind) {
  se2.insert(s[ind]);
  s2 += s[ind];
  balance();
}

void rem(int ind) {
  if (se2.count(s[ind])) {
    s2 -= s[ind];
    se2.erase(se2.find(s[ind]));
  } else {
    se.erase(se.find(s[ind]));
  }
  balance(); 
}

void edit(int l, int r) {
  while (cl > l) add(--cl);
  while (cr < r) add(++cr);
  while (cl < l) rem(cl++);
  while (cr > r) rem(cr--);
}

long long solve(int l, int r, int optl, int optr) {
  if (l > r) {
    return -LLONG_MAX;
  }
  int mid = (l + r) >> 1;
  long long ret = -LLONG_MAX;
  int opt = -1; 
  for (int i = min(mid, optr); i >= optl; --i) {
    edit(i, mid);
    if ((int) se2.size() == k) {
      long long val = pref[mid] - pref[i - 1] + s2;
      if (val > ret) {
        ret = val;
        opt = i;
        lx[mid] = i;
      }
    }
  }
  dp[mid] = ret;
  ret = max(ret, solve(l, mid - 1, optl, opt));
  ret = max(ret, solve(mid + 1, r, opt, optr));
  return ret; 
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) {
    cin >> c[i]; 
    pref[i] = pref[i - 1] - c[i];
  }
  for (int i = 1; i <= n; ++i) {
    cin >> s[i];
  }
  for (int i = 0; i < k; ++i) {
    dp[i] = -LLONG_MAX;
  }
  cl = 1, cr = 0;
  long long ans = solve(k, n, 1, n);
  int lst = -1; 
  for (int i = 1; i <= n; ++i) {
    if (lst != -1) {
      pre[i] = lx[lst];
    } else {
      pre[i] = 1; 
    }
    if (dp[i] == ans) {
      lst = i;
    }
  }
  for (int i = n, j = n; i >= 1; --i) {
    if (dp[i] != ans) {
      continue; 
    }
    if (j > i) {
      j = i;
    }
    while (j >= pre[i]) {
      edit(j, i);
      if (pref[i] - pref[j - 1] + s2 == ans && (int) se2.size() == k) {
        int mn = *se2.begin();
        to_add[j].push_back(mn);
        to_rem[i].push_back(mn);
      }
      if (j > pre[i]) {
        j--;        
      } else {
        break; 
      }
    }
  }
  multiset<int> ss;
  for (int i = 1; i <= n; ++i) {
    for (int j : to_add[i]) {
      ss.insert(j);
    }
    if (!ss.empty() && *ss.begin() <= s[i]) {
      ok[i] = true;
    }
    for (int j : to_rem[i]) {
      ss.erase(ss.find(j));
    }
  }
  cout << ans << '\n';
  for (int i = 1; i <= n; ++i) {
    cout << ok[i];
  }
  return 0;
}

Subtask #0

0.0 / 0.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	21084 KB	Output is correct
2	Correct	4 ms	21084 KB	Output is correct

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	21080 KB	Output is correct
2	Correct	3 ms	21084 KB	Output is correct
3	Correct	3 ms	21084 KB	Output is correct
4	Correct	3 ms	21080 KB	Output is correct
5	Correct	4 ms	21084 KB	Output is correct
6	Correct	4 ms	21084 KB	Output is correct
7	Correct	3 ms	20912 KB	Output is correct
8	Correct	5 ms	21084 KB	Output is correct
9	Correct	4 ms	21084 KB	Output is correct
10	Correct	3 ms	20924 KB	Output is correct
11	Correct	4 ms	21080 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	21080 KB	Output is correct
2	Correct	3 ms	21084 KB	Output is correct
3	Correct	3 ms	21084 KB	Output is correct
4	Correct	3 ms	21080 KB	Output is correct
5	Correct	4 ms	21084 KB	Output is correct
6	Correct	4 ms	21084 KB	Output is correct
7	Correct	3 ms	20912 KB	Output is correct
8	Correct	5 ms	21084 KB	Output is correct
9	Correct	4 ms	21084 KB	Output is correct
10	Correct	3 ms	20924 KB	Output is correct
11	Correct	4 ms	21080 KB	Output is correct
12	Correct	3 ms	21080 KB	Output is correct
13	Correct	3 ms	21084 KB	Output is correct
14	Correct	3 ms	21084 KB	Output is correct
15	Correct	3 ms	21084 KB	Output is correct
16	Correct	4 ms	21084 KB	Output is correct
17	Correct	4 ms	21084 KB	Output is correct
18	Correct	3 ms	21084 KB	Output is correct
19	Correct	3 ms	21172 KB	Output is correct
20	Correct	4 ms	21084 KB	Output is correct
21	Correct	4 ms	21084 KB	Output is correct
22	Correct	3 ms	21084 KB	Output is correct
23	Correct	9 ms	21520 KB	Output is correct
24	Correct	17 ms	21340 KB	Output is correct
25	Correct	30 ms	21408 KB	Output is correct
26	Correct	36 ms	21340 KB	Output is correct
27	Correct	32 ms	21588 KB	Output is correct
28	Correct	14 ms	21304 KB	Output is correct
29	Correct	26 ms	21336 KB	Output is correct

Subtask #3

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	21336 KB	Output is correct
2	Correct	561 ms	30032 KB	Output is correct
3	Correct	825 ms	34972 KB	Output is correct
4	Correct	943 ms	36176 KB	Output is correct
5	Correct	985 ms	31608 KB	Output is correct
6	Correct	942 ms	29884 KB	Output is correct
7	Correct	2472 ms	45432 KB	Output is correct
8	Correct	930 ms	33112 KB	Output is correct
9	Correct	796 ms	28728 KB	Output is correct
10	Correct	810 ms	29348 KB	Output is correct

Subtask #4

25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	21336 KB	Output is correct
2	Correct	561 ms	30032 KB	Output is correct
3	Correct	825 ms	34972 KB	Output is correct
4	Correct	943 ms	36176 KB	Output is correct
5	Correct	985 ms	31608 KB	Output is correct
6	Correct	942 ms	29884 KB	Output is correct
7	Correct	2472 ms	45432 KB	Output is correct
8	Correct	930 ms	33112 KB	Output is correct
9	Correct	796 ms	28728 KB	Output is correct
10	Correct	810 ms	29348 KB	Output is correct
11	Correct	3 ms	21080 KB	Output is correct
12	Correct	565 ms	30028 KB	Output is correct
13	Correct	853 ms	34972 KB	Output is correct
14	Correct	1014 ms	36008 KB	Output is correct
15	Correct	1014 ms	31744 KB	Output is correct
16	Correct	895 ms	29776 KB	Output is correct
17	Correct	2584 ms	45544 KB	Output is correct
18	Correct	929 ms	32948 KB	Output is correct
19	Correct	815 ms	28724 KB	Output is correct
20	Correct	753 ms	28272 KB	Output is correct
21	Correct	3 ms	21080 KB	Output is correct
22	Correct	4 ms	21340 KB	Output is correct
23	Correct	3 ms	21136 KB	Output is correct
24	Correct	4 ms	21084 KB	Output is correct
25	Correct	3 ms	21084 KB	Output is correct
26	Correct	4 ms	21084 KB	Output is correct
27	Correct	3 ms	21084 KB	Output is correct
28	Correct	5 ms	21084 KB	Output is correct
29	Correct	3 ms	21084 KB	Output is correct
30	Correct	5 ms	21084 KB	Output is correct
31	Correct	1492 ms	35488 KB	Output is correct
32	Correct	1145 ms	30028 KB	Output is correct
33	Correct	2146 ms	36892 KB	Output is correct
34	Correct	1895 ms	29676 KB	Output is correct
35	Correct	1576 ms	29520 KB	Output is correct
36	Correct	2471 ms	34324 KB	Output is correct
37	Correct	1010 ms	28400 KB	Output is correct

Subtask #5

45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	21084 KB	Output is correct
2	Correct	4 ms	21084 KB	Output is correct
3	Correct	4 ms	21080 KB	Output is correct
4	Correct	3 ms	21084 KB	Output is correct
5	Correct	3 ms	21084 KB	Output is correct
6	Correct	3 ms	21080 KB	Output is correct
7	Correct	4 ms	21084 KB	Output is correct
8	Correct	4 ms	21084 KB	Output is correct
9	Correct	3 ms	20912 KB	Output is correct
10	Correct	5 ms	21084 KB	Output is correct
11	Correct	4 ms	21084 KB	Output is correct
12	Correct	3 ms	20924 KB	Output is correct
13	Correct	4 ms	21080 KB	Output is correct
14	Correct	3 ms	21080 KB	Output is correct
15	Correct	3 ms	21084 KB	Output is correct
16	Correct	3 ms	21084 KB	Output is correct
17	Correct	3 ms	21084 KB	Output is correct
18	Correct	4 ms	21084 KB	Output is correct
19	Correct	4 ms	21084 KB	Output is correct
20	Correct	3 ms	21084 KB	Output is correct
21	Correct	3 ms	21172 KB	Output is correct
22	Correct	4 ms	21084 KB	Output is correct
23	Correct	4 ms	21084 KB	Output is correct
24	Correct	3 ms	21084 KB	Output is correct
25	Correct	9 ms	21520 KB	Output is correct
26	Correct	17 ms	21340 KB	Output is correct
27	Correct	30 ms	21408 KB	Output is correct
28	Correct	36 ms	21340 KB	Output is correct
29	Correct	32 ms	21588 KB	Output is correct
30	Correct	14 ms	21304 KB	Output is correct
31	Correct	26 ms	21336 KB	Output is correct
32	Correct	3 ms	21336 KB	Output is correct
33	Correct	561 ms	30032 KB	Output is correct
34	Correct	825 ms	34972 KB	Output is correct
35	Correct	943 ms	36176 KB	Output is correct
36	Correct	985 ms	31608 KB	Output is correct
37	Correct	942 ms	29884 KB	Output is correct
38	Correct	2472 ms	45432 KB	Output is correct
39	Correct	930 ms	33112 KB	Output is correct
40	Correct	796 ms	28728 KB	Output is correct
41	Correct	810 ms	29348 KB	Output is correct
42	Correct	3 ms	21080 KB	Output is correct
43	Correct	565 ms	30028 KB	Output is correct
44	Correct	853 ms	34972 KB	Output is correct
45	Correct	1014 ms	36008 KB	Output is correct
46	Correct	1014 ms	31744 KB	Output is correct
47	Correct	895 ms	29776 KB	Output is correct
48	Correct	2584 ms	45544 KB	Output is correct
49	Correct	929 ms	32948 KB	Output is correct
50	Correct	815 ms	28724 KB	Output is correct
51	Correct	753 ms	28272 KB	Output is correct
52	Correct	3 ms	21080 KB	Output is correct
53	Correct	4 ms	21340 KB	Output is correct
54	Correct	3 ms	21136 KB	Output is correct
55	Correct	4 ms	21084 KB	Output is correct
56	Correct	3 ms	21084 KB	Output is correct
57	Correct	4 ms	21084 KB	Output is correct
58	Correct	3 ms	21084 KB	Output is correct
59	Correct	5 ms	21084 KB	Output is correct
60	Correct	3 ms	21084 KB	Output is correct
61	Correct	5 ms	21084 KB	Output is correct
62	Correct	1492 ms	35488 KB	Output is correct
63	Correct	1145 ms	30028 KB	Output is correct
64	Correct	2146 ms	36892 KB	Output is correct
65	Correct	1895 ms	29676 KB	Output is correct
66	Correct	1576 ms	29520 KB	Output is correct
67	Correct	2471 ms	34324 KB	Output is correct
68	Correct	1010 ms	28400 KB	Output is correct
69	Correct	3 ms	21084 KB	Output is correct
70	Correct	483 ms	30036 KB	Output is correct
71	Correct	811 ms	34896 KB	Output is correct
72	Correct	962 ms	36184 KB	Output is correct
73	Correct	926 ms	31736 KB	Output is correct
74	Correct	865 ms	29880 KB	Output is correct
75	Correct	2240 ms	45452 KB	Output is correct
76	Correct	830 ms	33112 KB	Output is correct
77	Correct	746 ms	28740 KB	Output is correct
78	Correct	720 ms	29272 KB	Output is correct
79	Correct	3 ms	21080 KB	Output is correct
80	Correct	3 ms	21084 KB	Output is correct
81	Correct	3 ms	21136 KB	Output is correct
82	Correct	3 ms	21080 KB	Output is correct
83	Correct	3 ms	21140 KB	Output is correct
84	Correct	4 ms	21084 KB	Output is correct
85	Correct	3 ms	21084 KB	Output is correct
86	Correct	3 ms	21084 KB	Output is correct
87	Correct	4 ms	21080 KB	Output is correct
88	Correct	3 ms	21084 KB	Output is correct
89	Correct	1396 ms	35488 KB	Output is correct
90	Correct	939 ms	30232 KB	Output is correct
91	Correct	1765 ms	36800 KB	Output is correct
92	Correct	1728 ms	28712 KB	Output is correct
93	Correct	1632 ms	29528 KB	Output is correct
94	Correct	2462 ms	34388 KB	Output is correct
95	Correct	1006 ms	28248 KB	Output is correct
96	Correct	8 ms	21336 KB	Output is correct
97	Correct	17 ms	21340 KB	Output is correct
98	Correct	31 ms	17488 KB	Output is correct
99	Correct	25 ms	17492 KB	Output is correct
100	Correct	21 ms	17564 KB	Output is correct
101	Correct	13 ms	17244 KB	Output is correct
102	Correct	25 ms	19404 KB	Output is correct
103	Correct	3477 ms	37844 KB	Output is correct
104	Correct	1829 ms	29420 KB	Output is correct
105	Correct	1919 ms	28756 KB	Output is correct
106	Correct	2765 ms	31188 KB	Output is correct
107	Correct	2671 ms	33488 KB	Output is correct
108	Correct	3724 ms	34884 KB	Output is correct
109	Correct	2050 ms	42060 KB	Output is correct
110	Correct	2910 ms	40136 KB	Output is correct
111	Correct	1037 ms	31960 KB	Output is correct
112	Correct	2238 ms	33876 KB	Output is correct