Submission #896066

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
896066	2023-12-31T16:00:32 Z	cadmiumsky	Chorus (JOI23_chorus)	C++17	40 / 100	4 ms	2396 KB

chorus

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 505;
const ll inf = 1e9 + 5;

int B[nmax];

ll dp[nmax][nmax];

ll sum_under[nmax], cnt_under[nmax];
ll sum_pref[nmax];

namespace CHT {
  struct Line {
    ll m, b;
    Line(ll a, ll c): m(a), b(c) {;}
    ll operator()(const ll& x) const { return m * x + b; }
  };
  
  bool bad(Line second, Line last, Line nv) {
    return (nv.b - last.b) * (second.m - nv.m) < (nv.b - second.b) * (last.m - nv.m); 
  }
  
  vector<Line> st;
  int ptr;
  
  void push(Line a) {
    while(sz(st) > 1 && bad(rbegin(st)[1], rbegin(st)[0], a)) st.pop_back();
    st.emplace_back(a);
  }
  
  ll query(int P) {
    ptr = min(ptr, sz(st) - 1);
    while(ptr + 1 < sz(st) && st[ptr](P) > st[ptr + 1](P))
      ptr++;
    return st[ptr](P);
  }
  
  void clear() {
    st.clear();
    ptr = 0;
  }
}

signed main() {
  cin.tie(0) -> sync_with_stdio(0);
  int n, k;
  cin >> n >> k;
  
  int cnt[2] = {0, 0};
  char ch;
  for(int i = 0; i < 2 * n; i++) {
    cin >> ch;
    if(ch == 'A')
      cnt[0]++;
    else
      B[++cnt[1]] = cnt[0];
      //cerr << cnt[0] << '\n';
  }
  
  ll fixing = 0;
  for(int i = 1; i <= n; i++) {
    int target = max(B[i - 1], i);
    fixing += max(0, target - B[i]);
    B[i] += max(0, target - B[i]);
  }
  
  for(int i = 1; i <= n; i++)
    cnt_under[B[i]]++,
    sum_under[B[i]] += B[i],
    sum_pref[i] = sum_pref[i - 1] + B[i];
  
  for(int i = 1; i <= n; i++)
    cnt_under[i] += cnt_under[i - 1],
    sum_under[i] += sum_under[i - 1];
  
  //for(int i = 1; i <= n; i++)
    //cout << B[i] << ' ';
  //cout << '\n';
  
  for(int i = 1; i <= n; i++)
    dp[0][i] = inf;
  dp[0][n + 1] = 0;
  
  for(int dim = 1; dim <= k; dim++) {
    
    int last_nv = n;
    
    CHT::clear();
    
    for(int i = n; i > 0; i--) {
      
      while(last_nv >= B[i]) {
        CHT::push(CHT::Line(last_nv, -sum_under[last_nv] + cnt_under[last_nv] * last_nv + last_nv + dp[dim - 1][last_nv + 1]));
        last_nv--;
      }
      
      dp[dim][i] = CHT::query(-i) + sum_pref[i - 1];
    }
  }
  
  cout << dp[k][1] + fixing << '\n';
  
  
  
  
}

Subtask #1
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 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	0 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	0 ms	348 KB	Output is correct
9	Correct	1 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	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 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	348 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	0 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	0 ms	348 KB	Output is correct
9	Correct	1 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	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	1 ms	604 KB	Output is correct
18	Correct	1 ms	860 KB	Output is correct
19	Correct	2 ms	1372 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	4 ms	2396 KB	Output is correct
23	Correct	4 ms	2396 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	4 ms	2396 KB	Output is correct
26	Correct	4 ms	2140 KB	Output is correct
27	Correct	1 ms	1116 KB	Output is correct
28	Correct	2 ms	1116 KB	Output is correct

Subtask #3
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 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	0 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	0 ms	348 KB	Output is correct
9	Correct	1 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	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	1 ms	604 KB	Output is correct
18	Correct	1 ms	860 KB	Output is correct
19	Correct	2 ms	1372 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	4 ms	2396 KB	Output is correct
23	Correct	4 ms	2396 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	4 ms	2396 KB	Output is correct
26	Correct	4 ms	2140 KB	Output is correct
27	Correct	1 ms	1116 KB	Output is correct
28	Correct	2 ms	1116 KB	Output is correct
29	Runtime error	1 ms	604 KB	Execution killed with signal 11
30	Halted	0 ms	0 KB	-

Subtask #4
0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 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	0 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	0 ms	348 KB	Output is correct
9	Correct	1 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	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	1 ms	604 KB	Output is correct
18	Correct	1 ms	860 KB	Output is correct
19	Correct	2 ms	1372 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	4 ms	2396 KB	Output is correct
23	Correct	4 ms	2396 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	4 ms	2396 KB	Output is correct
26	Correct	4 ms	2140 KB	Output is correct
27	Correct	1 ms	1116 KB	Output is correct
28	Correct	2 ms	1116 KB	Output is correct
29	Runtime error	1 ms	604 KB	Execution killed with signal 11
30	Halted	0 ms	0 KB	-

Subtask #5
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 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	0 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	0 ms	348 KB	Output is correct
9	Correct	1 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	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	1 ms	604 KB	Output is correct
18	Correct	1 ms	860 KB	Output is correct
19	Correct	2 ms	1372 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	4 ms	2396 KB	Output is correct
23	Correct	4 ms	2396 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	4 ms	2396 KB	Output is correct
26	Correct	4 ms	2140 KB	Output is correct
27	Correct	1 ms	1116 KB	Output is correct
28	Correct	2 ms	1116 KB	Output is correct
29	Runtime error	1 ms	604 KB	Execution killed with signal 11
30	Halted	0 ms	0 KB	-

Submission #896066

Compilation message

Subtask #1 16.0 / 16.0

Subtask #2 24.0 / 24.0

Subtask #3 0 / 21.0

Subtask #4 0 / 26.0

Subtask #5 0 / 13.0

Subtask #1
16.0 / 16.0

Subtask #2
24.0 / 24.0

Subtask #3
0 / 21.0

Subtask #4
0 / 26.0

Subtask #5
0 / 13.0