oj.uz

Submission #1060770

# Submission time Handle Problem Language Result Execution time Memory
1060770 2024-08-15T22:23:24 Z MilosMilutinovic Tricks of the Trade (CEOI23_trade) C++14
50 / 100
 2039 ms 163956 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 250000;

const int MAX = (int) 1.00001e9;

int root[N * 60], ch[N * 60][2], cnt[N * 60], tsz;
long long sum[N * 60];

void Modify(int& x, int y, int l, int r, int i) {
  x = ++tsz;
  ch[x][0] = ch[y][0];
  ch[x][1] = ch[y][1];
  sum[x] = sum[y] + i;
  cnt[x] = cnt[y] + 1;
  if (l == r) {
    return;
  }
  int mid = (l + r) >> 1;
  if (i <= mid) {
    Modify(ch[x][0], ch[y][0], l, mid, i);
  } else {
    Modify(ch[x][1], ch[y][1], mid + 1, r, i);
  }
}

int Walk(int x, int y, int l, int r, int k) {
  if (l == r) {
    return l;
  }
  int mid = (l + r) >> 1;
  if (cnt[ch[x][1]] - cnt[ch[y][1]] >= k) {
    return Walk(ch[x][1], ch[y][1], mid + 1, r, k);
  } else {
    return Walk(ch[x][0], ch[y][0], l, mid, k - (cnt[ch[x][1]] - cnt[ch[y][1]]));
  }
}

int QueryCnt(int x, int y, int l, int r, int ll, int rr) {
  if (ll <= l && r <= rr) {
    return cnt[x] - cnt[y];
  }
  int mid = (l + r) >> 1;
  if (rr <= mid) {
    return QueryCnt(ch[x][0], ch[y][0], l, mid, ll, rr);
  } else if (ll > mid) {
    return QueryCnt(ch[x][1], ch[y][1], mid + 1, r, ll, rr);
  } else {
    return QueryCnt(ch[x][0], ch[y][0], l, mid, ll, rr) + QueryCnt(ch[x][1], ch[y][1], mid + 1, r, ll, rr);
  }
}

long long QuerySum(int x, int y, int l, int r, int ll, int rr) {
  if (ll <= l && r <= rr) {
    return sum[x] - sum[y];
  }
  int mid = (l + r) >> 1;
  if (rr <= mid) {
    return QuerySum(ch[x][0], ch[y][0], l, mid, ll, rr);
  } else if (ll > mid) {
    return QuerySum(ch[x][1], ch[y][1], mid + 1, r, ll, rr);
  } else {
    return QuerySum(ch[x][0], ch[y][0], l, mid, ll, rr) + QuerySum(ch[x][1], ch[y][1], mid + 1, r, ll, rr);
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<int> c(n);
  for (int i = 0; i < n; i++) {
    cin >> c[i];
  }
  vector<int> s(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i];
  }
  vector<long long> pref(n);
  for (int i = 0; i < n; i++) {
    pref[i] = (i == 0 ? 0LL : pref[i - 1]) + c[i];
  }
  for (int i = 0; i < n; i++) {
    if (i > 0) {
      root[i] = root[i - 1];
    }
    Modify(root[i], root[i], 0, MAX, s[i]);
  }
  const long long inf = (long long) -1e18;
  long long res = inf;
  auto Calc = [&](int l, int r) {
    if (r - l + 1 < k) {
      return inf;
    }
    long long ret = -(pref[r] - (l == 0 ? 0LL : pref[l - 1]));
    int el = Walk(root[r], l == 0 ? 0 : root[l - 1], 0, MAX, k);
    int c = QueryCnt(root[r], l == 0 ? 0 : root[l - 1], 0, MAX, el + 1, MAX);
    ret += QuerySum(root[r], l == 0 ? 0 : root[l - 1], 0, MAX, el + 1, MAX);
    ret += el * 1LL * (k - c);
    return ret;
  };
  function<void(int, int, int, int)> Solve = [&](int l, int r, int optl, int optr) {
    if (l > r) {
      return;
    }
    int mid = (l + r) >> 1;
    int opt = min(optl, mid);
    long long best = Calc(opt, mid);
    for (int i = optl; i <= min(mid, optr); i++) {
      long long v = Calc(i, mid);
      if (v > best) {
        best = v;
        opt = i;
      }
    }
    res = max(res, best);
    Solve(l, mid - 1, optl, opt);
    Solve(mid + 1, r, opt, optr);
  };
  Solve(0, n - 1, 0, n - 1);
  cout << res << '\n';
  return 0;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 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 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 604 KB Partially correct
5 Partially correct 0 ms 604 KB Partially correct
6 Partially correct 1 ms 604 KB Partially correct
7 Partially correct 1 ms 600 KB Partially correct
8 Partially correct 1 ms 604 KB Partially correct
9 Partially correct 1 ms 604 KB Partially correct
10 Partially correct 1 ms 604 KB Partially correct
11 Partially correct 1 ms 600 KB Partially correct

Subtask #2
5.0 / 10.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 604 KB Partially correct
5 Partially correct 0 ms 604 KB Partially correct
6 Partially correct 1 ms 604 KB Partially correct
7 Partially correct 1 ms 600 KB Partially correct
8 Partially correct 1 ms 604 KB Partially correct
9 Partially correct 1 ms 604 KB Partially correct
10 Partially correct 1 ms 604 KB Partially correct
11 Partially correct 1 ms 600 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 604 KB Partially correct
16 Partially correct 0 ms 604 KB Partially correct
17 Partially correct 1 ms 600 KB Partially correct
18 Partially correct 1 ms 604 KB Partially correct
19 Partially correct 1 ms 604 KB Partially correct
20 Partially correct 1 ms 604 KB Partially correct
21 Partially correct 1 ms 604 KB Partially correct
22 Partially correct 1 ms 600 KB Partially correct
23 Partially correct 3 ms 5908 KB Partially correct
24 Partially correct 30 ms 5980 KB Partially correct
25 Partially correct 27 ms 5980 KB Partially correct
26 Partially correct 30 ms 5980 KB Partially correct
27 Partially correct 17 ms 5980 KB Partially correct
28 Partially correct 19 ms 6128 KB Partially correct
29 Partially correct 10 ms 6128 KB Partially correct

Subtask #3
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Partially correct
2 Partially correct 1061 ms 159576 KB Partially correct
3 Partially correct 1006 ms 163924 KB Partially correct
4 Partially correct 1784 ms 162384 KB Partially correct
5 Partially correct 1912 ms 163796 KB Partially correct
6 Partially correct 1612 ms 161820 KB Partially correct
7 Partially correct 1967 ms 162900 KB Partially correct
8 Partially correct 962 ms 162384 KB Partially correct
9 Partially correct 1073 ms 160816 KB Partially correct
10 Partially correct 1033 ms 161472 KB Partially correct

Subtask #4
10.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Partially correct
2 Partially correct 1061 ms 159576 KB Partially correct
3 Partially correct 1006 ms 163924 KB Partially correct
4 Partially correct 1784 ms 162384 KB Partially correct
5 Partially correct 1912 ms 163796 KB Partially correct
6 Partially correct 1612 ms 161820 KB Partially correct
7 Partially correct 1967 ms 162900 KB Partially correct
8 Partially correct 962 ms 162384 KB Partially correct
9 Partially correct 1073 ms 160816 KB Partially correct
10 Partially correct 1033 ms 161472 KB Partially correct
11 Partially correct 0 ms 348 KB Partially correct
12 Partially correct 1079 ms 161828 KB Partially correct
13 Partially correct 1025 ms 162416 KB Partially correct
14 Partially correct 1759 ms 163956 KB Partially correct
15 Partially correct 1962 ms 162128 KB Partially correct
16 Partially correct 1662 ms 161916 KB Partially correct
17 Partially correct 1964 ms 163108 KB Partially correct
18 Partially correct 953 ms 163876 KB Partially correct
19 Partially correct 1035 ms 160628 KB Partially correct
20 Partially correct 1016 ms 161464 KB Partially correct
21 Partially correct 0 ms 344 KB Partially correct
22 Partially correct 0 ms 348 KB Partially correct
23 Partially correct 1 ms 604 KB Partially correct
24 Partially correct 0 ms 600 KB Partially correct
25 Partially correct 1 ms 604 KB Partially correct
26 Partially correct 1 ms 604 KB Partially correct
27 Partially correct 1 ms 604 KB Partially correct
28 Partially correct 1 ms 604 KB Partially correct
29 Partially correct 1 ms 604 KB Partially correct
30 Partially correct 1 ms 604 KB Partially correct
31 Partially correct 1006 ms 162240 KB Partially correct
32 Partially correct 2039 ms 163832 KB Partially correct
33 Partially correct 1875 ms 161900 KB Partially correct
34 Partially correct 1593 ms 161620 KB Partially correct
35 Partially correct 1487 ms 161412 KB Partially correct
36 Partially correct 1616 ms 162272 KB Partially correct
37 Partially correct 1362 ms 161644 KB Partially correct

Subtask #5
25.0 / 45.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB Partially correct
2 Partially correct 0 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 0 ms 348 KB Partially correct
6 Partially correct 1 ms 604 KB Partially correct
7 Partially correct 0 ms 604 KB Partially correct
8 Partially correct 1 ms 604 KB Partially correct
9 Partially correct 1 ms 600 KB Partially correct
10 Partially correct 1 ms 604 KB Partially correct
11 Partially correct 1 ms 604 KB Partially correct
12 Partially correct 1 ms 604 KB Partially correct
13 Partially correct 1 ms 600 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 604 KB Partially correct
18 Partially correct 0 ms 604 KB Partially correct
19 Partially correct 1 ms 600 KB Partially correct
20 Partially correct 1 ms 604 KB Partially correct
21 Partially correct 1 ms 604 KB Partially correct
22 Partially correct 1 ms 604 KB Partially correct
23 Partially correct 1 ms 604 KB Partially correct
24 Partially correct 1 ms 600 KB Partially correct
25 Partially correct 3 ms 5908 KB Partially correct
26 Partially correct 30 ms 5980 KB Partially correct
27 Partially correct 27 ms 5980 KB Partially correct
28 Partially correct 30 ms 5980 KB Partially correct
29 Partially correct 17 ms 5980 KB Partially correct
30 Partially correct 19 ms 6128 KB Partially correct
31 Partially correct 10 ms 6128 KB Partially correct
32 Partially correct 0 ms 348 KB Partially correct
33 Partially correct 1061 ms 159576 KB Partially correct
34 Partially correct 1006 ms 163924 KB Partially correct
35 Partially correct 1784 ms 162384 KB Partially correct
36 Partially correct 1912 ms 163796 KB Partially correct
37 Partially correct 1612 ms 161820 KB Partially correct
38 Partially correct 1967 ms 162900 KB Partially correct
39 Partially correct 962 ms 162384 KB Partially correct
40 Partially correct 1073 ms 160816 KB Partially correct
41 Partially correct 1033 ms 161472 KB Partially correct
42 Partially correct 0 ms 348 KB Partially correct
43 Partially correct 1079 ms 161828 KB Partially correct
44 Partially correct 1025 ms 162416 KB Partially correct
45 Partially correct 1759 ms 163956 KB Partially correct
46 Partially correct 1962 ms 162128 KB Partially correct
47 Partially correct 1662 ms 161916 KB Partially correct
48 Partially correct 1964 ms 163108 KB Partially correct
49 Partially correct 953 ms 163876 KB Partially correct
50 Partially correct 1035 ms 160628 KB Partially correct
51 Partially correct 1016 ms 161464 KB Partially correct
52 Partially correct 0 ms 344 KB Partially correct
53 Partially correct 0 ms 348 KB Partially correct
54 Partially correct 1 ms 604 KB Partially correct
55 Partially correct 0 ms 600 KB Partially correct
56 Partially correct 1 ms 604 KB Partially correct
57 Partially correct 1 ms 604 KB Partially correct
58 Partially correct 1 ms 604 KB Partially correct
59 Partially correct 1 ms 604 KB Partially correct
60 Partially correct 1 ms 604 KB Partially correct
61 Partially correct 1 ms 604 KB Partially correct
62 Partially correct 1006 ms 162240 KB Partially correct
63 Partially correct 2039 ms 163832 KB Partially correct
64 Partially correct 1875 ms 161900 KB Partially correct
65 Partially correct 1593 ms 161620 KB Partially correct
66 Partially correct 1487 ms 161412 KB Partially correct
67 Partially correct 1616 ms 162272 KB Partially correct
68 Partially correct 1362 ms 161644 KB Partially correct
69 Partially correct 0 ms 348 KB Partially correct
70 Partially correct 1130 ms 161624 KB Partially correct
71 Partially correct 995 ms 162204 KB Partially correct
72 Partially correct 1773 ms 163948 KB Partially correct
73 Partially correct 1947 ms 163788 KB Partially correct
74 Partially correct 1624 ms 163412 KB Partially correct
75 Partially correct 1964 ms 162924 KB Partially correct
76 Partially correct 953 ms 162132 KB Partially correct
77 Partially correct 1054 ms 160596 KB Partially correct
78 Partially correct 1043 ms 162996 KB Partially correct
79 Partially correct 1 ms 348 KB Partially correct
80 Partially correct 0 ms 348 KB Partially correct
81 Partially correct 1 ms 604 KB Partially correct
82 Partially correct 1 ms 604 KB Partially correct
83 Partially correct 1 ms 604 KB Partially correct
84 Partially correct 1 ms 604 KB Partially correct
85 Partially correct 1 ms 604 KB Partially correct
86 Partially correct 1 ms 604 KB Partially correct
87 Partially correct 1 ms 604 KB Partially correct
88 Partially correct 1 ms 604 KB Partially correct
89 Partially correct 1010 ms 162388 KB Partially correct
90 Partially correct 1943 ms 162272 KB Partially correct
91 Partially correct 1852 ms 161876 KB Partially correct
92 Partially correct 1646 ms 163156 KB Partially correct
93 Partially correct 1483 ms 163104 KB Partially correct
94 Partially correct 1734 ms 160744 KB Partially correct
95 Partially correct 1421 ms 160340 KB Partially correct
96 Partially correct 3 ms 5980 KB Partially correct
97 Partially correct 30 ms 5980 KB Partially correct
98 Partially correct 26 ms 5980 KB Partially correct
99 Partially correct 30 ms 6128 KB Partially correct
100 Partially correct 18 ms 5980 KB Partially correct
101 Partially correct 20 ms 5980 KB Partially correct
102 Partially correct 11 ms 5980 KB Partially correct
103 Partially correct 1040 ms 162908 KB Partially correct
104 Partially correct 1604 ms 161620 KB Partially correct
105 Partially correct 1595 ms 163236 KB Partially correct
106 Partially correct 1632 ms 163232 KB Partially correct
107 Partially correct 148 ms 161620 KB Partially correct
108 Partially correct 908 ms 161344 KB Partially correct
109 Partially correct 962 ms 160340 KB Partially correct
110 Partially correct 1237 ms 162388 KB Partially correct
111 Partially correct 597 ms 162644 KB Partially correct
112 Partially correct 1344 ms 160412 KB Partially correct