oj.uz

Submission #882785

# Submission time Handle Problem Language Result Execution time Memory
882785 2023-12-03T17:50:49 Z MilosMilutinovic Chorus (JOI23_chorus) C++14
61 / 100
 7000 ms 8148 KB 
#include <bits/stdc++.h>
 
using namespace std;

struct line {
  long long k, n;
  void init() {
    k = 0;
    n = (long long) 1e18;
  }
  long long val(long long x) {
    return k * x + n;
  }
};

const int MAX = 5e6;

line li[MAX];
int ls[MAX], rs[MAX], tsz, root;

void Update(int& x, int l, int r, line ln) {
  if (!x) {
    x = ++tsz;
    li[x].init();
  }
  int mid = l + r >> 1;
  if (li[x].val(mid) > ln.val(mid)) {
    swap(li[x], ln);
  }
  if (l == r) {
    return;
  }
  if (ln.val(l) < li[x].val(l)) {
    Update(ls[x], l, mid, ln);
  } else {
    Update(rs[x], mid + 1, r, ln);
  }
}

long long Query(int x, int l, int r, int i) {
  if (!x) {
    return (long long) 1e18;
  }
  if (l == r) {
    return li[x].val(i);
  }
  int mid = l + r >> 1;
  if (i <= mid) {
    return min(Query(ls[x], l, mid, i), li[x].val(i));
  } else {
    return min(Query(rs[x], mid + 1, r, i), li[x].val(i));
  }
}

void clear_seg() {
  while (tsz > 0) {
    ls[tsz] = 0;
    rs[tsz] = 0;
    li[tsz].init();
    tsz -= 1;
  }
  root = 0;
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  vector<int> a, b;
  for (int i = 0; i < 2 * n; i++) {
    if (s[i] == 'A') {
      a.push_back(i);
    } else {
      b.push_back(i);
    }
  }
  vector<int> ia(2 * n);
  for (int i = 0; i < n; i++) {
    ia[a[i]] = i + 1;
  }
  vector<int> pref(2 * n);
  for (int i = 0; i < 2 * n; i++) {
    if (i > 0) {
      pref[i] = pref[i - 1];
    }
    pref[i] += (s[i] == 'A' ? 1 : 0);
  }
  vector<int> ib(2 * n);
  for (int i = 0; i < n; i++) {
    ib[b[i]] = pref[b[i]];
  }
  auto Solve = [&](int L, int R) {
    int res = 0;
    for (int i = L; i <= R; i++) {
      res += max(0, ia[a[R]] - ib[b[i]]);
    }
    return res;
  };
  for (int i = 0; i < n; i++) {
    if (i > 0) {
      pref[i] = pref[i - 1];
    } else {
      pref[i] = 0;
    }
    pref[i] += ib[b[i]];
  }
  auto GetSum = [&](int L, int R) {
    return pref[R] - (L == 0 ? 0 : pref[L - 1]);
  };
  const int inf = (int) 1e9;
  vector<long long> dp(n + 1, inf);
  dp[0] = 0;
  for (int foo = 0; foo < k; foo++) {
    vector<long long> new_dp(n + 1, inf);
    int ptr = -1;
    multiset<long long> st;
    clear_seg();
    for (int i = 0; i < n; i++) {
      st.insert(dp[i]);
      while (ptr + 1 <= i && ia[a[i]] >= ib[b[ptr + 1]]) {
        ptr += 1;
        line cur;
        cur.k = -ptr;
        cur.n = dp[ptr] + (ptr == 0 ? 0 : pref[ptr - 1]);
        Update(root, 0, n, cur);
        st.erase(st.find(dp[ptr]));
      }
      if (!st.empty()) {
        new_dp[i + 1] = min(new_dp[i + 1], *st.begin());
      }
      if (ptr != -1) {
        new_dp[i + 1] = min(new_dp[i + 1], Query(root, 0, n, ia[a[i]]) + ia[a[i]] * 1LL * (ptr + 1) - pref[ptr]);
      }
    }
    swap(dp, new_dp);
  }
  cout << dp[n] << '\n';
  return 0;
}

Compilation message

chorus.cpp: In function 'void Update(int&, int, int, line)':
chorus.cpp:26:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |   int mid = l + r >> 1;
      |             ~~^~~
chorus.cpp: In function 'long long int Query(int, int, int, int)':
chorus.cpp:47:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |   int mid = l + r >> 1;
      |             ~~^~~
chorus.cpp: In function 'int main()':
chorus.cpp:95:8: warning: variable 'Solve' set but not used [-Wunused-but-set-variable]
   95 |   auto Solve = [&](int L, int R) {
      |        ^~~~~
chorus.cpp:110:8: warning: variable 'GetSum' set but not used [-Wunused-but-set-variable]
  110 |   auto GetSum = [&](int L, int R) {
      |        ^~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 2 ms 2396 KB Output is correct
18 Correct 9 ms 2396 KB Output is correct
19 Correct 33 ms 2536 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 25 ms 2396 KB Output is correct
23 Correct 25 ms 2396 KB Output is correct
24 Correct 2 ms 2396 KB Output is correct
25 Correct 30 ms 2396 KB Output is correct
26 Correct 28 ms 2396 KB Output is correct
27 Correct 12 ms 2392 KB Output is correct
28 Correct 12 ms 2396 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 2 ms 2396 KB Output is correct
18 Correct 9 ms 2396 KB Output is correct
19 Correct 33 ms 2536 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 25 ms 2396 KB Output is correct
23 Correct 25 ms 2396 KB Output is correct
24 Correct 2 ms 2396 KB Output is correct
25 Correct 30 ms 2396 KB Output is correct
26 Correct 28 ms 2396 KB Output is correct
27 Correct 12 ms 2392 KB Output is correct
28 Correct 12 ms 2396 KB Output is correct
29 Correct 1738 ms 4864 KB Output is correct
30 Correct 4877 ms 4852 KB Output is correct
31 Correct 1195 ms 4856 KB Output is correct
32 Correct 1 ms 2652 KB Output is correct
33 Correct 2 ms 4700 KB Output is correct
34 Correct 3255 ms 4900 KB Output is correct
35 Correct 3260 ms 4924 KB Output is correct
36 Correct 12 ms 4700 KB Output is correct
37 Correct 1020 ms 4880 KB Output is correct
38 Correct 3502 ms 4864 KB Output is correct
39 Correct 2285 ms 4884 KB Output is correct
40 Correct 1590 ms 4856 KB Output is correct
41 Correct 1593 ms 4696 KB Output is correct
42 Correct 1318 ms 5000 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 2 ms 2396 KB Output is correct
18 Correct 9 ms 2396 KB Output is correct
19 Correct 33 ms 2536 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 25 ms 2396 KB Output is correct
23 Correct 25 ms 2396 KB Output is correct
24 Correct 2 ms 2396 KB Output is correct
25 Correct 30 ms 2396 KB Output is correct
26 Correct 28 ms 2396 KB Output is correct
27 Correct 12 ms 2392 KB Output is correct
28 Correct 12 ms 2396 KB Output is correct
29 Correct 1738 ms 4864 KB Output is correct
30 Correct 4877 ms 4852 KB Output is correct
31 Correct 1195 ms 4856 KB Output is correct
32 Correct 1 ms 2652 KB Output is correct
33 Correct 2 ms 4700 KB Output is correct
34 Correct 3255 ms 4900 KB Output is correct
35 Correct 3260 ms 4924 KB Output is correct
36 Correct 12 ms 4700 KB Output is correct
37 Correct 1020 ms 4880 KB Output is correct
38 Correct 3502 ms 4864 KB Output is correct
39 Correct 2285 ms 4884 KB Output is correct
40 Correct 1590 ms 4856 KB Output is correct
41 Correct 1593 ms 4696 KB Output is correct
42 Correct 1318 ms 5000 KB Output is correct
43 Execution timed out 7011 ms 8148 KB Time limit exceeded
44 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 2 ms 2396 KB Output is correct
18 Correct 9 ms 2396 KB Output is correct
19 Correct 33 ms 2536 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 25 ms 2396 KB Output is correct
23 Correct 25 ms 2396 KB Output is correct
24 Correct 2 ms 2396 KB Output is correct
25 Correct 30 ms 2396 KB Output is correct
26 Correct 28 ms 2396 KB Output is correct
27 Correct 12 ms 2392 KB Output is correct
28 Correct 12 ms 2396 KB Output is correct
29 Correct 1738 ms 4864 KB Output is correct
30 Correct 4877 ms 4852 KB Output is correct
31 Correct 1195 ms 4856 KB Output is correct
32 Correct 1 ms 2652 KB Output is correct
33 Correct 2 ms 4700 KB Output is correct
34 Correct 3255 ms 4900 KB Output is correct
35 Correct 3260 ms 4924 KB Output is correct
36 Correct 12 ms 4700 KB Output is correct
37 Correct 1020 ms 4880 KB Output is correct
38 Correct 3502 ms 4864 KB Output is correct
39 Correct 2285 ms 4884 KB Output is correct
40 Correct 1590 ms 4856 KB Output is correct
41 Correct 1593 ms 4696 KB Output is correct
42 Correct 1318 ms 5000 KB Output is correct
43 Execution timed out 7011 ms 8148 KB Time limit exceeded
44 Halted 0 ms 0 KB -