| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1083230 |
2024-09-02T18:51:12 Z |
kes0716 |
Chorus (JOI23_chorus) |
C++17 |
|
10 ms |
14988 KB |
#include <bits/stdc++.h>
using namespace std;
char s[2000009];
typedef long long ll;
const ll INF = (ll)3e18;
ll a[1000009], psum[1000009], dp[1000009];
int cnt[1000009];
int tree[1<<21]; //(i, j) -> dp[i][j] + cost(j, *)
ll cost(int k, int j){
int idx = lower_bound(a+k, a+j, k-1) - a;
return psum[j-1] - psum[idx-1] - (ll)(k-1) * (j-idx);
}
pair<ll, int> evaluate(int idx, int x){
if(idx == -1)
return make_pair(INF, 0);
return make_pair(dp[idx] + 2*cost(idx, x), cnt[idx] + 1);
}
void update(int v, int l, int r, int idx){
int mid = (l+r)/2;
if(evaluate(tree[v], mid) > evaluate(idx, mid))
swap(idx, tree[v]);
if(evaluate(idx, l).first < evaluate(tree[v], l).first)
update(2*v, l, mid, idx);
else if(evaluate(idx, r).first < evaluate(tree[v], r).first)
update(2*v+1, mid+1, r, idx);
}
pair<ll, int> query(int v, int l, int r, int x){
pair<ll, int> ans = evaluate(tree[v], x);
int mid = (l+r)/2;
if(l==r)
return ans;
if(x <= mid)
ans = min(ans, query(2*v, l, mid, x));
if(x > mid)
ans = min(ans, query(2*v+1, mid+1, r, x));
return ans;
}
int main(){
int n, k, i, j, j2, cur = 0, cnt2 = 0;
scanf("%d %d", &n, &k);
scanf(" %s", s);
for(i=0; i<2*n; i++){
if(s[i] == 'A'){
a[++cnt2] = cur;
}
else
cur++;
}
for(i=1; i<=n; i++)
psum[i] = psum[i-1] + a[i];
ll lo = 0, hi = (ll)1e12, lambda;
while(1){
memset(tree, -1, sizeof(tree));
lambda = (lo+hi)>>1;
dp[1] = 0;
update(1, 1, n+1, 1);
for(j=2; j<=n+1; j++){
pair<ll, int> temp = query(1, 1, n+1, j);
dp[j] = min(INF, 2*lambda+1+temp.first);
cnt[j]= temp.second;
//printf("j=%d dp=%lld cnt=%d\n", j, dp[j], cnt[j]);
update(1, 1, n+1, j);
}
if(lo==hi)
break;
if(cnt[n+1] > k)
lo = lambda+1;
else
hi = lambda;
}
memset(tree, -1, sizeof(tree));
lambda = lo;
dp[1] = 0;
update(1, 1, n+1, 1);
for(j=2; j<=n+1; j++){
pair<ll, int> temp = query(1, 1, n+1, j);
dp[j] = min(INF, 2*lambda+temp.first);
cnt[j]= temp.second;
update(1, 1, n+1, j);
}
assert((dp[n+1] - cnt[n+1]*(2*lambda)) % 2 == 0);
printf("%lld\n", (dp[n+1] - cnt[n+1]*(2*lambda))>>1);
return 0;
}
Compilation message
chorus.cpp: In function 'int main()':
chorus.cpp:39:21: warning: unused variable 'j2' [-Wunused-variable]
39 | int n, k, i, j, j2, cur = 0, cnt2 = 0;
| ^~
chorus.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | scanf("%d %d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~~
chorus.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | scanf(" %s", s);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14940 KB |
Output is correct |
| 2 |
Correct |
9 ms |
14940 KB |
Output is correct |
| 3 |
Correct |
8 ms |
14940 KB |
Output is correct |
| 4 |
Correct |
8 ms |
14988 KB |
Output is correct |
| 5 |
Correct |
8 ms |
14940 KB |
Output is correct |
| 6 |
Incorrect |
10 ms |
14940 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14940 KB |
Output is correct |
| 2 |
Correct |
9 ms |
14940 KB |
Output is correct |
| 3 |
Correct |
8 ms |
14940 KB |
Output is correct |
| 4 |
Correct |
8 ms |
14988 KB |
Output is correct |
| 5 |
Correct |
8 ms |
14940 KB |
Output is correct |
| 6 |
Incorrect |
10 ms |
14940 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14940 KB |
Output is correct |
| 2 |
Correct |
9 ms |
14940 KB |
Output is correct |
| 3 |
Correct |
8 ms |
14940 KB |
Output is correct |
| 4 |
Correct |
8 ms |
14988 KB |
Output is correct |
| 5 |
Correct |
8 ms |
14940 KB |
Output is correct |
| 6 |
Incorrect |
10 ms |
14940 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14940 KB |
Output is correct |
| 2 |
Correct |
9 ms |
14940 KB |
Output is correct |
| 3 |
Correct |
8 ms |
14940 KB |
Output is correct |
| 4 |
Correct |
8 ms |
14988 KB |
Output is correct |
| 5 |
Correct |
8 ms |
14940 KB |
Output is correct |
| 6 |
Incorrect |
10 ms |
14940 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14940 KB |
Output is correct |
| 2 |
Correct |
9 ms |
14940 KB |
Output is correct |
| 3 |
Correct |
8 ms |
14940 KB |
Output is correct |
| 4 |
Correct |
8 ms |
14988 KB |
Output is correct |
| 5 |
Correct |
8 ms |
14940 KB |
Output is correct |
| 6 |
Incorrect |
10 ms |
14940 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
