oj.uz

Submission #882801

# Submission time Handle Problem Language Result Execution time Memory
882801 2023-12-03T18:06:22 Z MilosMilutinovic Chorus (JOI23_chorus) C++14
40 / 100
 7000 ms 604 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]];
  }
  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 Cost = [&](int L, int R) {
    long long ret = 0;
    for (int i = L; i <= R; i++) {
      ret += max(0, ia[a[R]] - ib[b[i]]);
    }
    return ret;
  }; 
  auto Solve = [&](long long mid) {
    vector<pair<long long, int>> dp(n + 1);
    for (int i = 0; i <= n; i++) {
      dp[i] = {1e18, 0};
    }
    dp[0] = {0, 0};
    for (int i = 0; i < n; i++) {
      for (int j = i; j < n; j++) {
        long long new_dp = dp[i].first + Cost(i, j);
        dp[j + 1] = min(dp[j + 1], {new_dp + mid, dp[i].second + 1});
      }
    }
    return dp[n];
  };
  long long low = 0, high = 1e15, p = 0;
  while (low <= high) {
    long long mid = low + high >> 1;
    pair<long long, int> res = Solve(mid);
    if (res.second <= k) {
      p = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  pair<long long, int> res = Solve(p);
  cout << res.first - p * k << '\n';
  /* 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:126:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  126 |     long long mid = low + high >> 1;
      |                     ~~~~^~~~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 48 ms 348 KB Output is correct
18 Correct 896 ms 464 KB Output is correct
19 Correct 887 ms 460 KB Output is correct
20 Correct 889 ms 464 KB Output is correct
21 Correct 884 ms 468 KB Output is correct
22 Correct 880 ms 344 KB Output is correct
23 Correct 874 ms 464 KB Output is correct
24 Correct 867 ms 472 KB Output is correct
25 Correct 871 ms 468 KB Output is correct
26 Correct 931 ms 480 KB Output is correct
27 Correct 911 ms 600 KB Output is correct
28 Correct 923 ms 472 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 48 ms 348 KB Output is correct
18 Correct 896 ms 464 KB Output is correct
19 Correct 887 ms 460 KB Output is correct
20 Correct 889 ms 464 KB Output is correct
21 Correct 884 ms 468 KB Output is correct
22 Correct 880 ms 344 KB Output is correct
23 Correct 874 ms 464 KB Output is correct
24 Correct 867 ms 472 KB Output is correct
25 Correct 871 ms 468 KB Output is correct
26 Correct 931 ms 480 KB Output is correct
27 Correct 911 ms 600 KB Output is correct
28 Correct 923 ms 472 KB Output is correct
29 Execution timed out 7032 ms 604 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 48 ms 348 KB Output is correct
18 Correct 896 ms 464 KB Output is correct
19 Correct 887 ms 460 KB Output is correct
20 Correct 889 ms 464 KB Output is correct
21 Correct 884 ms 468 KB Output is correct
22 Correct 880 ms 344 KB Output is correct
23 Correct 874 ms 464 KB Output is correct
24 Correct 867 ms 472 KB Output is correct
25 Correct 871 ms 468 KB Output is correct
26 Correct 931 ms 480 KB Output is correct
27 Correct 911 ms 600 KB Output is correct
28 Correct 923 ms 472 KB Output is correct
29 Execution timed out 7032 ms 604 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 48 ms 348 KB Output is correct
18 Correct 896 ms 464 KB Output is correct
19 Correct 887 ms 460 KB Output is correct
20 Correct 889 ms 464 KB Output is correct
21 Correct 884 ms 468 KB Output is correct
22 Correct 880 ms 344 KB Output is correct
23 Correct 874 ms 464 KB Output is correct
24 Correct 867 ms 472 KB Output is correct
25 Correct 871 ms 468 KB Output is correct
26 Correct 931 ms 480 KB Output is correct
27 Correct 911 ms 600 KB Output is correct
28 Correct 923 ms 472 KB Output is correct
29 Execution timed out 7032 ms 604 KB Time limit exceeded
30 Halted 0 ms 0 KB -